1.1 问题描述

对于一个非负整数 $x$，定义 $f(x)$ 为进行如下操作的结果：

1. 在十进制下，将 $x$ 写成一个字符串；
2. 将字符串所有字符排序；
3. 将字符串看成一个数 $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}$。

特别地，编号为偶数的子任务满足：存在一个整数 $k$ 使得 $n = 10^k$。

大样例