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

Задача . G. Новый год и правильный порядок


Обозначим за S(n) число, которое получается, если переставить цифры числа n в порядке возрастания. Например, S(1) = 1, S(5) = 5, S(50394) = 3459, S(353535) = 333555.

Вам дано число X, вычислите по модулю 109 + 7.

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

Первая строка содержит одно целое число X (1 ≤ X ≤ 10700).

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

Выведите одно целое число: ответ на задачу.

Примечание

Первые несколько значений S равны 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 12. Сумма этих величин равна 195.


Примеры
№Входные данныеВыходные данные
1
21
195
2
345342
390548434
Статистика успешных решений по компиляторам
 Кол-во
Python1
С++4