设 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。