1.1 问题描述
对于一个非负整数 $x$,定义 $f(x)$ 为进行如下操作的结果:
- 在十进制下,将 $x$ 写成一个字符串;
- 将字符串所有字符排序;
- 将字符串看成一个数 $y$,则 $f(x) = y$。
给定 $n$,求 $\sum\limits_{x=1}^n f(x) \bmod 10^9+7$。
1.2 输入格式
输入一行一个整数 $n$。
1.3 输出格式
输出一行一个整数表示答案。
1.4 样例 $1$ 输入
10
1.5 样例 $1$ 输出
46
1.6 样例 $1$ 解释
当 $1 \le x \le 9$ 时,$f(x) = x$,且 $f(10) = 1$。 答案为 $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 1 = 46$。
1.7 样例 $2,3,4$
见下发文件。
1.8 数据规模与约定
对于所有数据,$1 \le n < 10^{10000}$。
子任务编号 | 分值 | 其他限制 |
---|---|---|
$1$ | $10$ | $n < 10^6$ |
$2,3$ | $15$ | $n < 10^{50}$ |
$4,5$ | $15$ | $n < 10^{500}$ |
$6,7$ | $15$ | 无 |
特别地,编号为偶数的子任务满足:存在一个整数 $k$ 使得 $n = 10^k$。