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.


-----Examples-----
Input
6 2
38 56 49
7 3 4

Output
8

Input
8 2
1 22 3 44
5 4 3 2

Output
32400



-----Note-----

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

Difficulty: MEDIUM_HARD
Tags: Sorting

Mathematics
Skill types: Sorting

Starter code:

Solutions:
import sys
(n, k) = sys.stdin.readline().split()
n = int(n)
k = int(k)
a = [int(x) for x in sys.stdin.readline().split()]
b = [int(x) for x in sys.stdin.readline().split()]
MOD = 10 ** 9 + 7
res = 1
for i in range(0, n // k):
	lo = b[i] * 10 ** (k - 1) - 1
	up = (b[i] + 1) * 10 ** (k - 1) - 1
	tmp = (10 ** k - 1) // a[i] - up // a[i] + lo // a[i] + 1
	res = res * tmp
	res = res % MOD
print(res)


from math import ceil
(n, k) = map(int, input().split())
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
p = 10 ** k
ans = 1
for i in range(n // k):
	(x, y) = (arr1[i], arr2[i])
	(a, b) = (y * 10 ** (k - 1), (y + 1) * 10 ** (k - 1))
	ans *= ceil(p / x) - (ceil(b / x) - ceil(a / x))
	ans %= 10 ** 9 + 7
print(ans)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = 1
for i in range(n // k):
	ans *= (10 ** k - 1) // a[i] - ((b[i] + 1) * 10 ** (k - 1) - 1) // a[i] + (b[i] * 10 ** (k - 1) - 1) // a[i] + 1
	ans %= mod
print(ans)


(n, k) = [int(tmp) for tmp in input().split()]
a = [int(tmp) for tmp in input().split()]
b = [int(tmp) for tmp in input().split()]
BIG = 10 ** 9 + 7
m = n // k
ans = [0] * m
for i in range(m):
	ans[i] = (10 ** k + a[i] - 1) // a[i]
	x = 10 ** (k - 1) * b[i] % a[i]
	if x != 0:
		ans[i] -= (10 ** (k - 1) + x + a[i] - 1) // a[i] - 1
	else:
		ans[i] -= (10 ** (k - 1) + x + a[i] - 1) // a[i]
all_ans = 1
for i in range(m):
	all_ans = all_ans * ans[i] % BIG
print(all_ans)


def ndivide(k, a, b):
	return (b - a) // k + (b % k < a % k) + (a % k == 0)
(n, k) = (int(x) for x in input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
N = 1
for i in range(n // k):
	a = B[i] * 10 ** (k - 1)
	b = (B[i] + 1) * 10 ** (k - 1) - 1
	N *= (ndivide(A[i], 0, 10 ** k - 1) - ndivide(A[i], a, b)) % (10 ** 9 + 7)
	N %= 10 ** 9 + 7
print(N)


(n, k) = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
mod = 1000000007
ans = 1
for x in range(0, n // k):
	po = 10 ** (k - 1)
	p = c[x] * po
	q = (c[x] + 1) * po
	res = 0
	if p % b[x] == 0:
		res -= 1
	if q % b[x] == 0:
		res += 1
	if po * 10 % b[x] == 0:
		res -= 1
	res += 1
	res += 10 * po // b[x] - q // b[x] + p // b[x]
	ans = ans % mod * (res % mod) % mod
print(ans)


from math import *
MOD = 10 ** 9 + 7
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
temp = pow(10, k - 1)
ans = 1
for i in range(len(a)):
	totDiv = ceil(temp * 10 / a[i])
	num1 = temp * b[i]
	num2 = temp * (b[i] + 1)
	smaller = ceil(num1 / a[i])
	larger = ceil(num2 / a[i])
	totDiv += smaller - larger
	ans = ans * totDiv % MOD
print(int(ans))


(n, k) = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
MOD = 10 ** 9 + 7
ans = 1
for i in range(n // k):
	alls = (10 ** k - 1) // a[i] + 1
	subt = (b[i] * 10 ** (k - 1) + (10 ** (k - 1) - 1)) // a[i]
	subt -= (b[i] * 10 ** (k - 1) - 1) // a[i]
	alls -= subt
	ans *= alls
	ans %= MOD
print(ans)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 10 ** 9 + 7
ans = 1
for (ai, bi) in zip(a, b):
	if bi == 0:
		h = 10 ** (k - 1) - 1
		cnt = h // ai + 1
	else:
		h = bi * 10 ** (k - 1) + 10 ** (k - 1) - 1
		l = (bi - 1) * 10 ** (k - 1) + 10 ** (k - 1) - 1
		cnt = h // ai - l // ai
	ans *= (10 ** k - 1) // ai + 1 - cnt
	ans %= MOD
print(ans)


mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 1
for i in range(n // k):
	cnt = (10 ** k - 1) // a[i] - (10 ** (k - 1) * (b[i] + 1) - 1) // a[i]
	if b[i] != 0:
		cnt += (10 ** (k - 1) * b[i] - 1) // a[i] + 1
	ans = ans * cnt % mod
print(ans)


def c(a, b, k):
	v = (10 ** k - 1) // a + 1
	v -= (10 ** (k - 1) * (b + 1) - 1) // a - (10 ** (k - 1) * b - 1) // a
	return v
(MOD, v) = (1000000007, 1)
(n, k) = map(int, input().split())
for (a, b) in zip(map(int, input().split()), map(int, input().split())):
	v = v * c(a, b, k) % MOD
print(v)


import time
MM = 1000000007

def func(a, b, k):
	if b == 0:
		return divmod(10 ** k - 1, a)[0] - divmod(10 ** (k - 1) - 1, a)[0]
	else:
		return divmod(10 ** k - 1, a)[0] - divmod((b + 1) * 10 ** (k - 1) - 1, a)[0] + divmod(b * 10 ** (k - 1) - 1, a)[0] + 1
(n, k) = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
start = time.time()
s = 1
for i in range(divmod(n, k)[0]):
	s *= func(a[i], b[i], k)
	s = divmod(s, MM)[1]
print(s)
finish = time.time()


from math import ceil
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
m = 10 ** (k - 1)
ans = 1
for i in range(n // k):
	an = (10 ** k - 1) // a[i] + 1
	l = b[i] * m
	r = (b[i] + 1) * m - 1
	count = r // a[i] - ceil(l / a[i]) + 1
	ans = ans * (an - count) % (10 ** 9 + 7)
print(ans)


(n, k) = [int(i) for i in input().split()]
sum = 1
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
for i in range(n // k):
	if n == 0:
		x = (10 ** k - 1) // a[i] - ((b[i] + 1) * 10 ** (k - 1) - 1) // a[i]
	else:
		x = (10 ** k - 1) // a[i] - ((b[i] + 1) * 10 ** (k - 1) - 1) // a[i] + (b[i] * 10 ** (k - 1) - 1) // a[i] + 1
	sum *= x
	sum %= 10 ** 9 + 7
print(sum)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
t = 10 ** (k - 1)
res = 1
q = 10 ** 9 + 7
for i in range(n // k):
	res1 = ((t * 10 - 1) // a[i] + 1) % q
	z = (t * b[i] - 1) // a[i] + 1
	if b[i] == 0:
		z = 0
	x = (t * b[i] + t - 1) // a[i] + 1
	res1 = (res1 - x + z) % q
	res = res * res1 % q
print(res)


from math import *
(N, K) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 1
M = 10 ** 9 + 7
p = 10 ** K - 1
u = 10 ** (K - 1)
for i in range(N // K):
	ans *= p // a[i] + 1 - ((u * (b[i] + 1) + a[i] - 1) // a[i] - (b[i] * u + a[i] - 1) // a[i])
	ans %= M
print((ans + M) % M)


n1 = input()
(q, w) = n1.split()
n = int(q)
k = int(w)
n2 = input()
A1 = n2.split()
n3 = input()
B1 = n3.split()
x = ''
y = ''
A = []
B = []
for i in range(0, n // k):
	A.append(int(A1[i]))
	B.append(int(B1[i]))
for i in range(0, k - 1):
	x += '0'
	y += '9'
fin = 0
for i in range(0, n // k):
	ans = int('9' + y) // A[i] + 1
	h = int(str(B[i]) + x)
	g = int(str(B[i]) + y)
	d = g - g % A[i]
	if d >= h:
		ans -= (d - h) // A[i] + 1
	if fin == 0 and ans > 0:
		fin = 1
	fin = fin * ans % 1000000007
print(fin)


def cnt(l, r, x):
	return (r - l) // x + (l % x == 0) + (l % x > r % x)
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 1
for i in range(n // k):
	l = b[i] * pow(10, k - 1)
	r = (b[i] + 1) * pow(10, k - 1) - 1
	ans = ans * (cnt(0, pow(10, k) - 1, a[i]) - cnt(l, r, a[i])) % (pow(10, 9) + 7)
print(ans)


from math import *

def solve():
	res = 1
	for i in range(n // k):
		tmp = P
		tmp = ceil(tmp / a1[i])
		t = ceil(P / 10 * a2[i] / a1[i]) * a1[i]
		t = ceil((P - t - P // 10 * (9 - a2[i])) / a1[i])
		if t < 0:
			t = 0
		tmp -= t
		res = res * tmp % M
	print(res)
(n, k) = map(int, input().split())
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
M = int(1000000000.0 + 7)
P = tmp = pow(10, k)
solve()


import sys
(n, k) = map(int, sys.stdin.readline().split())
msa = [int(i) for i in sys.stdin.readline().split()]
msb = [int(i) for i in sys.stdin.readline().split()]
sch = 1
for i in range(n // k):
	cha = msa[i]
	chb = msb[i]
	chx = (pow(10, k) - 1) // cha + 1
	if chb != 0:
		chx = chx - (pow(10, k - 1) * (chb + 1) - 1) // cha + (pow(10, k - 1) * chb - 1) // cha
	else:
		chx = chx - (pow(10, k - 1) - 1) // cha - 1
	sch *= chx % 1000000007
sys.stdout.write(str(sch % 1000000007))


M = 10 ** 9 + 7

def good(k, a, b):
	t = (10 ** k - 1) // a + 1
	s = (b * 10 ** (k - 1) - 1) // a + 1
	e = ((b + 1) * 10 ** (k - 1) - 1) // a + 1
	return (t - (e - s)) % M

def total_good(k, ai, bi):
	p = 1
	for (a, b) in zip(ai, bi):
		p = p * good(k, a, b) % M
	return p
(n, k) = map(int, input().split())
assert n % k == 0
ai = map(int, input().split())
bi = map(int, input().split())
print(total_good(k, ai, bi))


from math import *
MOD = 1000000007
(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
res = 1
for i in range(n // k):
	cont = ceil(10 ** k / a[i]) - ceil((b[i] + 1) * 10 ** (k - 1) / a[i]) + ceil(b[i] * 10 ** (k - 1) / a[i])
	res = res * cont % MOD
print(res)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
answer = list()
for i in range(n // k):
	res = 0
	m = '1' + '0' * k
	m = int(m) - 1
	q = str(b[i]) + '9' * (k - 1)
	q = int(q)
	c = str(b[i] - 1) + '9' * (k - 1)
	c = int(c)
	c = max(c, -1)
	res = m // a[i] + 1 - q // a[i] + c // a[i]
	answer.append(res)
resa = 1
if sum(answer) == 0:
	print(0)
else:
	for i in answer:
		resa = resa * i % 1000000007
	print(resa)


def get_multypler(k, a, b):
	res = (10 ** k - 1) // a + 1
	bad_residue = (a - 10 ** (k - 1) * b % a) % a
	suf = 10 ** (k - 1) - 1
	minus = suf // a + (1 if bad_residue <= suf % a else 0)
	return res - minus
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 1
for i in range(n // k):
	ans *= get_multypler(k, a[i], b[i])
	ans %= 10 ** 9 + 7
print(ans)


(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
(res, MOD) = (1, int(1000000000.0 + 7))
pow10 = 10 ** k
for i in range(n // k):
	lo = pow10 // 10 * b[i] - 1
	up = pow10 // 10 * (b[i] + 1) - 1
	tmp = (pow10 - 1) // a[i] + 1
	tmp -= up // a[i]
	tmp += lo // a[i]
	res = res * tmp % MOD
print(res)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = n // k
ans = 1
for i in range(c):
	t_ans = (10 ** k - 1) // a[i] + 1 + b[i] * 10 ** (k - 1) // a[i] - (b[i] + 1) * 10 ** (k - 1) // a[i]
	if b[i] * 10 ** (k - 1) % a[i] == 0:
		t_ans -= 1
	if (b[i] + 1) * 10 ** (k - 1) % a[i] == 0:
		t_ans += 1
	ans *= t_ans
	ans = ans % (10 ** 9 + 7)
print(ans)


import math
(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = 1
for i in range(n // k):
	count = (10 ** k - 1) // a[i] + 1
	mmin = b[i] * 10 ** (k - 1)
	mmax = (b[i] + 1) * 10 ** (k - 1) - 1
	mcount = mmax // a[i] - math.ceil(mmin / a[i]) + 1
	c = c * (count - mcount) % (10 ** 9 + 7)
print(c)


import sys
(n, k) = map(int, input().split())

def getNumber(l, r, num):
	d = l // num
	if d * num < l:
		d += 1
	l = num * d
	if l > r:
		return 0
	return (r - l) // num + 1
ans = 1
mod = 10 ** 9 + 7
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(0, n // k):
	if b[i] == 0:
		ans *= getNumber(10 ** (k - 1), 10 ** k - 1, a[i]) % mod
	elif b[i] == 9:
		ans *= getNumber(0, 10 ** k - 1 - 10 ** (k - 1), a[i]) % mod
	else:
		ans *= (getNumber(0, 10 ** (k - 1) * b[i] - 1, a[i]) % mod + getNumber(10 ** (k - 1) * (b[i] + 1), 10 ** k - 1, a[i]) % mod) % mod
	ans %= mod
print(ans)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d = n // k
r = [0] * d
for i in range(d):
	r[i] = int('1' * k) * 9 // a[i] + 1
	x = int(str(b[i]) + (k - 1) * '9') // a[i] + 1
	if b[i] > 0:
		x -= int(str(b[i] - 1) + (k - 1) * '9') // a[i] + 1
	r[i] -= x
p = 1
for i in range(d):
	r[i] %= 10 ** 9 + 7
	p = p * r[i] % (10 ** 9 + 7)
print(p)


(n, k) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
assert n % k == 0
import math

def abc(k, censor):
	a = 10 ** k - 1
	b = censor * 10 ** (k - 1) + 10 ** (k - 1) - 1
	if censor == 0:
		c = 0
	else:
		c = (censor - 1) * 10 ** (k - 1) + 10 ** (k - 1) - 1
	return (a, b, c)

def numDiv(n, div):
	return int(n / div)
t = 1
mod = int(1000000000.0) + 7
for i in range(len(B)):
	(a, b, c) = abc(k, B[i])
	aa = numDiv(a, A[i])
	bb = numDiv(b, A[i])
	cc = numDiv(c, A[i])
	if B[i] != 0:
		cc += 1
	tt = aa - bb + cc
	t = t * tt % mod
print(t)


import math
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

def calc_ans(k, a, b):
	div = (10 ** k - 1) // a + 1
	b_min = b * 10 ** (k - 1)
	b_max = (b + 1) * 10 ** (k - 1) - 1
	d_min_inc = math.ceil(b_min / a)
	d_max_inc = math.floor(b_max / a)
	return div - (d_max_inc - d_min_inc + 1)
p = 10 ** 9 + 7
ans = 1
for (ai, bi) in zip(a, b):
	ans = ans * calc_ans(k, ai, bi) % p
print(ans)

def easy_calc(k, a, b):
	ans = 0
	for i in range(10 ** k):
		c = str(i)
		first = int(c[0]) if len(c) == k else 0
		if i % a == 0 and (not first == b):
			ans += 1
	return ans


(n, k) = map(int, input().split())
ara = list(map(int, input().split()))
arb = list(map(int, input().split()))
sum1 = 1
p_k = 10 ** k
p_k1 = 10 ** (k - 1)
p_k2 = 10 ** (k - 2)
M = 10 ** 9 + 7
for i in range(n // k):
	k = 0
	if p_k % ara[i] == 0:
		k = -1
	if (arb[i] + 1) * p_k1 % ara[i] == 0:
		k = k + 1
	if arb[i] * p_k1 % ara[i] == 0:
		k = k - 1
	sum1 *= p_k // ara[i] - p_k1 * (arb[i] + 1) // ara[i] + p_k1 * arb[i] // ara[i] + k + 1
	sum1 = sum1 % M
print(sum1 % (10 ** 9 + 7))


s = input()
ast = s.split(' ')
(n, k) = (int(ast[0]), int(ast[1]))
s = input()
a = [int(i) for i in s.split(' ')]
s = input()
b = [int(i) for i in s.split(' ')]
L = n // k
p = 10 ** k
r = 10 ** (k - 1)
rez = 1
for i in range(L):
	cnt = 0
	if b[i] > 0:
		cnt += (b[i] * r - 1) // a[i]
		cnt += (p - 1) // a[i]
		cnt -= ((b[i] + 1) * r - 1) // a[i]
		rez *= cnt + 1
	else:
		cnt += (p - 1) // a[i]
		cnt -= (r - 1) // a[i]
		rez *= cnt
	rez = rez % (10 ** 9 + 7)
print(rez)


def get_arr(Len):
	buff = input().split()
	a = []
	for i in range(Len):
		a.append(int(buff[i]))
	return a
base = int(1000000000.0 + 7)
buff = input().split()
n = int(buff[0])
k = int(buff[1])
a = get_arr(n // k)
b = get_arr(n // k)
c = []
for i in range(n // k):
	ans = 0
	if b[i] != 0:
		ans += (pow(10, k) - 1) // a[i]
		ans -= (b[i] * pow(10, k - 1) + pow(10, k - 1) - 1) // a[i]
		ans += ((b[i] - 1) * pow(10, k - 1) + pow(10, k - 1) - 1) // a[i]
		ans += 1
	else:
		ans = (pow(10, k) - 1) // a[i]
		ans -= (pow(10, k - 1) - 1) // a[i]
	c.append(ans % base)
ans = 1
for i in range(n // k):
	ans *= c[i]
	ans %= base
print(ans)


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 1
for i in range(n // k):
	count = 1 + (10 ** k - 1) // A[i]
	count -= (10 ** (k - 1) * (B[i] + 1) - 1) // A[i] - (10 ** (k - 1) * B[i] - 1) // A[i]
	ans = ans * count % (10 ** 9 + 7)
print(ans)


import math

def func(a, b, k):
	global highest
	global base
	start = b * base
	finish = start + base - 1
	lower = math.ceil(start / a)
	upper = math.floor(finish / a)
	fauls = upper - lower + 1
	ans = int(highest / a) + 1 - fauls
	return ans
inf = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
(n, k) = (inf[0], inf[1])
ans = [None] * int(n / k)
highest = 10 ** k - 1
base = 10 ** (k - 1)
w = 1
mod = 10 ** 9 + 7
for i in range(int(n / k)):
	w = w % mod * (func(a[i], b[i], k) % mod) % mod
w = w % mod
print(w)


R = lambda : map(int, input().split())
(n, k) = R()
t = 1
mod = 10 ** 9 + 7

def gn(x, p):
	if x < 0:
		return 0
	return x // p + 1

def solve(a, b, k):
	if k == 1:
		return 9 // a if b % a == 0 else 9 // a + 1
	m = b * pow(10, k - 1, a) % a
	w = 10 ** (k - 1) - 1 + m
	r = gn(10 ** k - 1, a) - (gn(w, a) - gn(m - 1, a))
	return r
a = list(R())
b = list(R())
for i in range(len(a)):
	t *= solve(a[i], b[i], k)
	t %= mod
print(t % mod)


(n, k) = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

def solve(n, k, As, Bs):
	mod = 10 ** 9 + 7
	c = 1
	for (a, b) in zip(As, Bs):
		c *= f(a, b, k, mod)
		c %= mod
	return c

def f(a, b, k, mod):
	total = (10 ** k - 1) // a + 1
	p = ((b + 1) * 10 ** (k - 1) - 1) // a
	q = (b * 10 ** (k - 1) - 1) // a
	return (total - p + q) % mod
print(solve(n, k, As, Bs))


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return [int(x) for x in input().split()]
(n, k) = mapin()
a = mapin()
b = mapin()
p = 10 ** k
ans = 1
m = 1000000007
for i in range(n // k):
	x = a[i]
	y = b[i]
	aa = y * 10 ** (k - 1)
	bb = (y + 1) * 10 ** (k - 1)
	ans *= ceil(p, x) - (ceil(bb, x) - ceil(aa, x))
	ans %= m
print(ans)


import itertools as it
import functools
import operator
import collections
import math
import sys
BASE = 1000000007

def count(k, a, b):
	x = count_multiples(a, 0, 10 ** k - 1)
	y = count_multiples(a, b * 10 ** (k - 1), (b + 1) * 10 ** (k - 1) - 1)
	return x - y

def count_multiples(a, _from, _to):
	if _from == 0:
		return _to // a - (_from - 1) // a
	else:
		return _to // a - (_from - 1) // a

def solve(xs, ys, n, k):
	result = 1
	for (a, b) in zip(xs, ys):
		result = result * count(k, a, b) % BASE
	return result

def main():
	[n, k] = [int(i) for i in input().strip().split()]
	xs = [int(i) for i in input().strip().split()]
	ys = [int(i) for i in input().strip().split()]
	assert len(xs) == len(ys) == n // k
	result = solve(xs, ys, n, k)
	print(result)

def __starting_point():
	main()
__starting_point()


mask = 10 ** 9 + 7

def count(a, x):
	return x // a + 1
(n, k) = map(int, input().split())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
big = 10 ** k - 1
small = 10 ** (k - 1)
result = 1
for i in range(n // k):
	(a, b) = (aa[i], bb[i])
	sum = 0
	sum += count(a, big)
	sum -= count(a, (b + 1) * small - 1)
	if b != 0:
		sum += count(a, b * small - 1)
	result = result * sum % mask
print(result)


def divisible(left, right, by):
	left_div = (left + by - 1) // by * by
	right -= left_div
	if right < 0:
		return 0
	return right // by + 1
(n, k) = map(int, input().split())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
ans = 1
mod = 1000000007
for (a, b) in zip(aa, bb):
	ans = ans * (divisible(0, 10 ** k - 1, a) - divisible(b * 10 ** (k - 1), (b + 1) * 10 ** (k - 1) - 1, a)) % mod
print(ans)


def main():
	(n, k) = map(int, input().split())
	(tk0, tk1, res) = (10 ** (k - 1), 10 ** k, 1)
	for (a, b) in zip(map(int, input().split()), map(int, input().split())):
		res *= (tk1 - 1) // a - ((tk0 * (b + 1) - 1) // a - (tk0 * b - 1) // a - 1 if b else (tk0 - 1) // a)
		res %= 1000000007
	print(res)
main()


inp = list(map(int, input().split()))
n = inp[0]
k = inp[1]
a = list(map(int, input().split()))
b = list(map(int, input().split()))
cnt = 10 ** k
cnt1 = 10 ** (k - 1)
l = n // k
ans = 1
for i in range(l):
	c = (cnt - 1) // a[i] + 1
	c -= ((b[i] + 1) * cnt1 - 1) // a[i] + 1 - ((b[i] * cnt1 - 1) // a[i] + 1 if b[i] >= 0 else 0)
	ans *= c
	ans %= int(1000000000.0 + 7)
print(ans)
import time, sys
sys.stderr.write('{0:.3f} ms\n'.format(time.clock() * 1000))


MOD = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
(k1, k2, ans) = (10 ** k, 10 ** (k - 1), 1)
for i in range(n // k):
	(z, x) = (a[i], b[i])
	if b[i] > 0:
		c = (x * k2 - 1) // z + (k1 - 1) // z - ((x + 1) * k2 - 1) // z + 1
	else:
		c = (k1 - 1) // z - (k2 - 1) // z
	ans = ans * c % MOD
print(ans)


from math import ceil
from math import floor
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ln = n // k
p = 1
mod = 1000000007
for i in range(ln):
	tmp = (10 ** k - 1) // a[i] + 1
	l = ceil(b[i] * 10 ** (k - 1) / a[i])
	r = floor(((b[i] + 1) * 10 ** (k - 1) - 1) / a[i])
	tmp -= r - l + 1
	p = p * tmp % mod
print(p)