← 返回题目列表

Codeforces · 908/G

G. 新年和原始订单

中文机器翻译题面 查看原题

设 S(n) 表示按排序顺序表示 n 的数字的数字。例如,S(1) = 1、S(5) = 5、S(50394) = 3459、S(353535) = 333555。

给定数字 X,计算 $$\sum_{1 \leq k \leq X} S(k)$$ 模 109 + 7。

输入

输入的第一行将包含整数 X (1 ≤ X ≤ 10700)。

输出

打印一个整数,即问题的答案。

示例

输入 #1

21

输出 #1

195

输入 #2

345342

输出 #2

390548434

注意

S 的前几个值是 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 12。这些值的总和是 195。