B. Паша и телефон
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Паша совсем недавно купил себе новый телефон jPager и начал вносить в него номера телефонов своих друзей. Каждый номер состоит ровно из n цифр.

Также у Паши есть число k и две последовательности длины n / k (n делится на k) a1, a2, ..., an / k и b1, b2, ..., bn / k. Разобьем телефонный номер на блоки длины k. Первый блок будет образован цифрами из телефонного номера, находящимися на позициях 1, 2,..., k, второй блок будет образован цифрами из телефонного номера, стоящими на позициях k + 1, k + 2, ..., 2·k и так далее. Паша считает телефонный номер хорошим, если i-й блок, представленный в виде целого числа, делится нацело на ai, и при этом этот блок не начинается с цифры bi.

Чтобы представить блок длины k в виде целого числа, выпишем его отдельно как последовательность c1, c2,...,ck. Теперь вычислим значение выражения c1·10k - 1 + c2·10k - 2 + ... + ck.

Паша просит вас посчитать количество хороших телефонных номеров длины n для данных k, ai и bi. Поскольку это число может быть большим, выведите остаток от деления его на 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, являющихся, по мнению Паши, хорошими.

Примеры
Входные данные
6 2
38 56 49
7 3 4
Выходные данные
8
Входные данные
8 2
1 22 3 44
5 4 3 2
Выходные данные
32400
Примечание

В первом тестовом примере хорошими телефонными номерами являются 000000, 000098, 005600, 005698, 380000, 380098, 385600, 385698.