Маска 3
(Время: 1 сек. Память: 32 Мб Сложность: 27%)
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
- символ «?» означает ровно одну произвольную цифру;
- символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300425.
На отрезке [L, R] найдите числа, удовлетворяющих маске M и делящиеся на натуральное число K без остатка. Запишите в ответе количество найденных чисел.
Входные данные
Первая строка входного файла INPUT.TXT содержит непустую маску M, состоящую не более, чем из 8 символов. Во второй строке записано натуральное число K (103 ⩽ K < 104). В третьей строке через пробел заданы числа L и R – диапазон поиска (1 ⩽ L ⩽ R ⩽ 108).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2?7*45?
1567
1 100000000
| 8 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
