A10148. Pasha and Phone

Pasha has recently bought a new phone jPager and started adding his friends' phone numbers there. Each phone number consists of exactly $n$ digits.

Also Pasha has a number $k$ and two sequences of length $n/k$ ( $n$ is divisible by $k$ ) $a_{1},a_{2},...,a_{n/k}$ and $b_{1},b_{2},...,b_{n/k}$ . Let's split the phone number into blocks of length $k$ . The first block will be formed by digits from the phone number that are on positions $1$ , $2$ ,..., $k$ , the second block will be formed by digits from the phone number that are on positions $k+1$ , $k+2$ , ..., $2·k$ and so on. Pasha considers a phone number good, if the $i$ -th block doesn't start from the digit $b_{i}$ and is divisible by $a_{i}$ if represented as an integer.

To represent the block of length $k$ as an integer, let's write it out as a sequence $c_{1}$ , $c_{2}$ ,..., $c_{k}$ . Then the integer is calculated as the result of the expression $c_{1}·10^{k-1}+c_{2}·10^{k-2}+...+c_{k}$ .

Pasha asks you to calculate the number of good phone numbers of length $n$ , for the given $k$ , $a_{i}$ and $b_{i}$ . As this number can be too big, print it modulo $10^{9}+7$ .

The first line of the input contains two integers $n$ and $k$ ( $1<=n<=100000$ , $1<=k<=min(n,9)$ ) — the length of all phone numbers and the length of each block, respectively. It is guaranteed that $n$ is divisible by $k$ .

The second line of the input contains $n/k$ space-separated positive integers — sequence $a_{1},a_{2},...,a_{n/k}$ ( $1<=a_{i}<10^{k}$ ).

The third line of the input contains $n/k$ space-separated positive integers — sequence $b_{1},b_{2},...,b_{n/k}$ ( $0<=b_{i}<=9$ ).

Print a single integer — the number of good phone numbers of length $n$ modulo $10^{9}+7$ .

In the first test sample good phone numbers are: 000000, 000098, 005600, 005698, 380000, 380098, 385600, 385698.