Олимпиадный тренинг

Задача . G. Очередная мемная задача


Задача

Темы: дп *2700

Назовем дробь \(\frac{x}{y}\) хорошей, если существует хотя бы одна дробь \(\frac{x'}{y'}\), удовлетворяющая следующим условиям: \(\frac{x}{y} = \frac{x'}{y'}\), \(1 \le x', y' \le 9\), цифра, обозначающая \(x'\), встречается хотя бы один раз в десятичной записи \(x\), и цифра, обозначающая \(y'\), встречается хотя бы один раз в десятичной записи \(y\). Например, \(\frac{26}{13}\) — хорошая дробь, так как \(\frac{26}{13} = \frac{2}{1}\).

Вам дано целое число \(n\). Посчитайте количество хороших дробей \(\frac{x}{y}\), для которых \(1 \le x \le n\) и \(1 \le y \le n\). Ответ может быть очень большим, поэтому выведите его по модулю \(998244353\).

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

В единственной строке входных данных записано одно целое число \(n\) (\(1 \le n < 10^{100}\)).

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

Выведите количество хороших дробей \(\frac{x}{y}\), для которых \(1 \le x \le n\) и \(1 \le y \le n\). Ответ может быть очень большим, поэтому выведите его по модулю \(998244353\).


Примеры
Входные данныеВыходные данные
1 42
150
2 3141592653589793238462643383279
459925407

time 4000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя