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

Рассмотрим десятичное представление некоторого целого числа. Будем называть число d-волшебным, если цифра d находится на всех чётных позициях десятичного представления числа и нигде больше.

Например, числа 1727374, 17, 1 являются 7-волшебными, а числа 77, 7, 123, 34, 71 не являются 7-волшебными. С другой стороны число 7 является, например, 0-волшебным, 123 является 2-волшебным, 34 является 4-волшебным, а 71 является 1-волшебным.

Вам нужно посчитать количество d-волшебных чисел в отрезке [a, b] кратных m. Поскольку ответ может быть очень большим, требуется найти его значение по модулю 109 + 7 (то есть нужно найти остаток при делении на число 109 + 7).

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

В первой строке находится пара целых числа m, d (1 ≤ m ≤ 2000, 0 ≤ d ≤ 9) — параметры описанные в условии задачи.

Во второй строке находится целое положительное число a в десятичном представлении (без лидирующих нулей).

В третьей строке находится целое положительное число b в десятичном представлении (без лидирующих нулей).

Гарантируется, что a ≤ b, а также количество цифр в числах a и b одинаково и не превосходит 2000.

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

Выведите целое число a — остаток при делении искомого количества d-волшебных чисел кратных m в отрезке [a, b] на число 109 + 7.

Примеры
Входные данные
2 6
10
99
Выходные данные
8
Входные данные
2 0
1
9
Выходные данные
4
Входные данные
19 7
1000
9999
Выходные данные
6
Примечание

Числа из ответа к первому примеру: 16, 26, 36, 46, 56, 76, 86 и 96.

Числа из ответа ко второму примеру: 2, 4, 6 и 8.

Числа из ответа к третьему примеру: 1767, 2717, 5757, 6707, 8797 и 9747.