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* ≤ 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).

提交代码