Имеется b блоков цифр, каждый из которых состоит ровно из n цифр, представленных во входных данных. Мокрая Акула выбирает ровно одну цифру из каждого блока и объединяет их в большое число в десятичной системе счисления. К примеру, если из первого блока выбрать 1, а из второго 2, то получится целое число 12.
Затем Мокрая Акула вычисляет остаток от деления получившегося числа на x. Определите количество таких способов выбрать по одной цифре в каждом блоке, чтобы получившийся остаток был в точности равен k. Поскольку это количество может оказаться достаточно большим, то выведите его по модулю 109 + 7.
Обратите внимание, что количество способов выбрать конкретную цифру в блоке равно количеству её вхождений. Например, существует 3 способа выбрать цифру 5 из блока 356789511115.
Выходные данные
Выведите количество способов выбрать в каждом блоке ровно одну цифру так, чтобы получившееся целое число давало остаток k при делении на x.
Примечание
Во втором примере можно получить числа 22, 26, 62 и 66, но все они не дают остаток 1 при делении на 2.
В третьем примере числа 11, 13, 21, 23, 31 и 33 дают остаток 1 по модулю 2. Каждое из этих числе можно составить единственным способом, так что ответ равен 6.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
12 1 5 10
3 5 6 7 8 9 5 1 1 1 1 5
|
3
|
|
2
|
3 2 1 2
6 2 2
|
0
|
|
3
|
3 2 1 2
3 1 2
|
6
|