Рассмотрим десятичное представление некоторого целого числа. Будем называть число 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).
Выходные данные
Выведите целое число a — остаток при делении искомого количества d-волшебных чисел кратных m в отрезке [a, b] на число 109 + 7.
Примечание
Числа из ответа к первому примеру: 16, 26, 36, 46, 56, 76, 86 и 96.
Числа из ответа ко второму примеру: 2, 4, 6 и 8.
Числа из ответа к третьему примеру: 1767, 2717, 5757, 6707, 8797 и 9747.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 6
10
99
|
8
|
|
2
|
2 0
1
9
|
4
|
|
3
|
19 7
1000
9999
|
6
|