New Year and Original Order

ID: 3936

远端评测题

2000ms

256MiB

难度: (无)

上传者:

标签>

math

*2800

Description

Let S(n) denote the number that represents the digits of n in sorted order. For example, S(1) = 1, S(5) = 5, S(50394) = 3459, S(353535) = 333555.

Given a number X, compute modulo 10⁹ + 7.

The first line of input will contain the integer X (1 ≤ X ≤ 10⁷⁰⁰).

Print a single integer, the answer to the question.

The first line of input will contain the integer X (1 ≤ X ≤ 10⁷⁰⁰).

Print a single integer, the answer to the question.

390548434

The first few values of S are 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 12. The sum of these values is 195.