|
Сложная рекурсия 3
(Время: 1 сек. Память: 64 Мб Сложность: 78%)
Обозначим через a % b остаток от деления натурального числа a на натуральное число b, а через a // b – целую часть от деления a на b. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
- F(n) = 1, если n = 0,
- F(n) = F(n // 10) × (n % 10), если n > 0 и n нечётно;
- F(n) = F(n // 10), если n > 0 и n чётно.
Определите количество значений n, таких что Left ≤ n ≤ Right, для которых F(n) = K. Так как количество значений может большим числом, то выведите ответ по модулю 998244353.
Входные данные
Входной файл INPUT.TXT в единственной строке содержит три числа Left, Right и K (1 ≤ Left < Right ≤ 101000; 2 ≤ K ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1 100 3 | 12 |
| 2 | 1 100 2 | 0 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
