Pasha 最近购买了一部新手机 jPager 并开始在那里添加他朋友的电话号码。每个电话号码均由 n 位数字组成。
Pasha 还有一个数字 k 和两个长度为 n / k(n 可被 k 整除)的序列 a1、a2、...、an / k 和 b1、b2、...、bn / k。让我们将电话号码分成长度为 k 的块。第一个块将由电话号码中位置 1, 2,..., k 的数字组成,第二块将由电话号码中位置 k + 1, k + 2, ..., 2·k 的数字形成,依此类推。如果第 i 个块不是从数字 bi 开始并且如果表示为整数则可被 ai 整除,则 Pasha 认为电话号码是好的。
为了将长度为 k 的块表示为整数,我们将其写为序列 c1, c2,...,ck。然后将整数计算为表达式 c1·10k - 1 + c2·10k - 2 + ... + ck 的结果。
Pasha 要求您计算给定 k、ai 和 bi 的长度为 n 的好电话号码的数量。由于这个数字可能太大,因此将其打印为 109 + 7 模。
输入
输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ min(n, 9)) - 分别是所有电话号码的长度和每个块的长度。保证n能被k整除。
输入的第二行包含 n / k 个空格分隔的正整数 — 序列 a1, a2, ..., an / k (1 ≤ ai < 10k)。
输入的第三行包含 n / k 个空格分隔的正整数 - 序列 b1, b2, ..., bn / k (0 ≤ bi ≤ 9)。
输出
打印一个整数——长度为 n 模 109 + 7 的有效电话号码的数量。
示例
输入 #1
6 2 38 56 49 7 3 4
输出 #1
8
输入 #2
8 2 1 22 3 44 5 4 3 2
输出 #2
32400
注意
在第一个测试样本中,好的电话号码是:000000、000098、005600、005698、380000、380098、385600、385698。