Задача . B. Паша и телефон

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

Также у Паши есть число k и две последовательности длины n / k (n делится на k) a₁, a₂, ..., a_n / k и b₁, b₂, ..., b_n / k. Разобьем телефонный номер на блоки длины k. Первый блок будет образован цифрами из телефонного номера, находящимися на позициях 1, 2,..., k, второй блок будет образован цифрами из телефонного номера, стоящими на позициях k + 1, k + 2, ..., 2·k и так далее. Паша считает телефонный номер хорошим, если i-й блок, представленный в виде целого числа, делится нацело на a_i, и при этом этот блок не начинается с цифры b_i.

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

Паша просит вас посчитать количество хороших телефонных номеров длины n для данных k, a_i и b_i. Поскольку это число может быть большим, выведите остаток от деления его на 10⁹ + 7.