Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

G. Новый год и правильный порядок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

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

Примеры
Входные данные
21
Выходные данные
195
Входные данные
345342
Выходные данные
390548434
Примечание

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