You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

定义 S(n) 为 整数n的每一位数字从小到大排序后得到的数字。

例如, S(1) = 1, S(5) = 5, S(50394) = 3459, S(353535) = 333555.

给出一个正整数 X, 求 $S(1)+S(2)+...+S(X)$模 $10^9+7$

。

输入格式

一行一个正整数 X .

输出格式

一行一个整数，表示计算结果。

输入样例1

21

输出样例1

195

样例解释1

在1到21上，函数 S 的取值分别为 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 12. 和为195.

输入样例2

345342

输出样例2

390548434

数据范围

$30\%， X\leq 10000$

$50\%， X\leq100000$

$100\%， X\leq10^{700}$