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$.

Input

The first line of the input contains two integers $*n*$ and $*k*$ ($1 ≤ *n* ≤ 100 000$, $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$).

Output

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

Note

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