Magry遇上了初雪第二弹

题目描述

嗯嗯，初雪那天，Magry像往常一样刷朋友圈，突然发现了这么一条新鲜值极高的消息，吓得他和他的小伙伴们都点了赞。

然后，据来自microhhh的小道消息，张导女票的电话号码相当神奇。这个号码是n位数字，被分成了每k个数一个小块（n能被k整除）。已知：数列ai(i=1,2,3,...,n/k)与bi(i=1,2,3,...,n/k，0<=bi<=min(n,9) )。它最后组成的号码需满足如下条件：

1.第i块的数须在 [0,10^k) 范围内且对a[i]取模得0；

2.第i块的数的首位不为b[i].

因此，Magry想知道张导女票神奇的电话号码有多少种可能呢（结果对1000000007取模）？

输入

多组输入数据，每组数据为3行。

第一行为n与k的值， 其中1 ≤ n ≤ 100 000, 1 ≤ k ≤ min(n, 9)，并且保证n能被k整除；

第二行为n/k个非负整数，为数列ai，其中1 ≤ ai < 10^k；

第三行为n/k个非负整数，为数列bi，其中0 ≤ bi ≤ 9。

输出

对于每组数据，输出一行，为所求可能性的个数。由于可能的结果很大，要求结果对1000000007取模。

输入样例

4 2
22 33
4 3

输出样例

12

样例解释

话说，这个电话号码是四位数，嗯。
然后呢，被分成了每2个数一块，共为2块。
接着呢，第一块的首位不为4，第二块的首位不为3.
于是乎，符合条件的号码有：
0000，0066，0099，2200，2266，2299，6600，6666，6699，8800，8866，8899
共计12种。
至于0033，2233，4400，4433，4466，4499，6633，8833这些可能根据上述规则就被枪毙了呦。
Oh, yeah!