Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Обозначим за 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.