CF595B.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 109 + 7.

帕沙最近购买了一部新手机“jPager”，并开始在其中添加朋友们的电话号码。每个电话号码恰好由 $n$ 位数字组成。

此外，帕沙还有一个整数 $k$，以及两个长度均为 $n/k$ 的序列（$n$ 可被 $k$ 整除）：$a_1, a_2, \dots, a_{n/k}$ 和 $b_1, b_2, \dots, b_{n/k}$。我们将电话号码划分为若干长度为 $k$ 的块：第 $1$ 块由电话号码中位置 $1, 2, \dots, k$ 上的数字构成；第 $2$ 块由位置 $k+1, k+2, \dots, 2k$ 上的数字构成；以此类推。帕沙认为一个电话号码是“好的”，当且仅当对每个 $i$，第 $i$ 个块不以数字 $b_i$ 开头，且该块作为整数表示时能被 $a_i$ 整除。

将长度为 $k$ 的块表示为数字序列 $c_1, c_2, \dots, c_k$，则其对应的整数值为表达式

$$c_1 \cdot 10^{k-1} + c_2 \cdot 10^{k-2} + \dots + c_k$$

的计算结果。

帕沙请你计算：给定 $k$、$a_i$ 和 $b_i$ 的前提下，长度为 $n$ 的“好”电话号码的总数。由于答案可能非常大，请输出其对 $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).

输入的第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 100\,000$，$1 ≤ k ≤ \min(n, 9)$），分别表示所有电话号码的长度以及每个分块的长度。保证 $n$ 能被 $k$ 整除。

输入的第二行包含 $n/k$ 个用空格分隔的正整数——序列 $a_1,\,a_2,\,...,\,a_{n/k}$（$1 ≤ a_i < 10^k$）。

输入的第三行包含 $n/k$ 个用空格分隔的正整数——序列 $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 109 + 7.

输出一个整数——长度为 $n$ 的“好”电话号码的个数对 $10^9 + 7$ 取模的结果。

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

在第一个测试样例中，好的电话号码有：000000、000098、005600、005698、380000、380098、385600、385698。