E. Мокрая Акула и блоки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Имеется b блоков цифр, каждый из которых состоит ровно из n цифр, представленных во входных данных. Мокрая Акула выбирает ровно одну цифру из каждого блока и объединяет их в большое число в десятичной системе счисления. К примеру, если из первого блока выбрать 1, а из второго 2, то получится целое число 12.

Затем Мокрая Акула вычисляет остаток от деления получившегося числа на x. Определите количество таких способов выбрать по одной цифре в каждом блоке, чтобы получившийся остаток был в точности равен k. Поскольку это количество может оказаться достаточно большим, то выведите его по модулю 109 + 7.

Обратите внимание, что количество способов выбрать конкретную цифру в блоке равно количеству её вхождений. Например, существует 3 способа выбрать цифру 5 из блока 356789511115.

Входные данные

В первой строке входных данных записаны четыре целых числа n, b, k и x (2 ≤ n ≤ 50 000, 1 ≤ b ≤ 109, 0 ≤ k < x ≤ 100, x ≥ 2) — количество цифр в одном блоке, количество блоков, требуемый остаток от деления на x и само число x соответственно.

В следующей строке записаны n цифр ai (1 ≤ ai ≤ 9) — содержимое каждого блока.

Выходные данные

Выведите количество способов выбрать в каждом блоке ровно одну цифру так, чтобы получившееся целое число давало остаток k при делении на x.

Примеры
Входные данные
12 1 5 10
3 5 6 7 8 9 5 1 1 1 1 5
Выходные данные
3
Входные данные
3 2 1 2
6 2 2
Выходные данные
0
Входные данные
3 2 1 2
3 1 2
Выходные данные
6
Примечание

Во втором примере можно получить числа 22, 26, 62 и 66, но все они не дают остаток 1 при делении на 2.

В третьем примере числа 11, 13, 21, 23, 31 и 33 дают остаток 1 по модулю 2. Каждое из этих числе можно составить единственным способом, так что ответ равен 6.