从 $$$1$$$ 到 $$$n$$$(含)的整数按字典顺序排序(将整数视为字符串)。结果得到数组$$$a_1, a_2, \dots, a_n$$$。
计算 $$$(\sum_{i = 1}^n ((i - a_i) \mod 998244353)) \mod 10^9 + 7$$$ 的值。
$$$x \mod y$$$ 这里表示 $$$x$$$ 除以 $$$y$$$ 后的余数。该余数始终为非负数,并且不超过 $$$y - 1$$$。例如,$$$5 \mod 3 = 2$$$,$$$(-1) \mod 6 = 5$$$。
输入
第一行包含单个整数 $$$n$$$ ($$$1 \leq n \leq 10^{12}$$$)。
输出
打印一个整数——所需的总和。
示例
输入 #1
3
输出 #1
0
输入 #2
12
输出 #2
994733045
输入 #3
21
输出 #3
978932159
输入#4
1000000000000
输出#4
289817887
注意
当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。
例如,$$$42$$$ 按字典顺序小于 $$$6$$$,因为它们的第一位数字不同,并且 $$$4 < 6$$$; $$$42 < 420$$$,因为 $$$42$$$ 是 $$$420$$$ 的前缀。
让我们将 $$$998244353$$$ 表示为 $$$M$$$。
在第一个示例中,数组 $$$a$$$ 等于 $$$[1, 2, 3]$$$。
- $$$(1 - 1) \mod M = 0 \mod M = 0$$$
- $$$(2 - 2) \mod M = 0 \mod M = 0$$$
- $$$(3 - 3) \mod M = 0 \mod M = 0$$$
因此,$$$(0 + 0 + 0) \mod 10^9 + 7 = 0$$$
在第二个示例中,数组 $$$a$$$ 等于 $$$[1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9]$$$。
- $$$(1 - 1) \mod M = 0 \mod M = 0$$$
- $$$(2 - 10) \mod M = (-8) \mod M = 998244345$$$
- $$$(3 - 11) \mod M = (-8) \mod M = 998244345$$$
- $$$(4 - 12) \mod M = (-8) \mod M = 998244345$$$
- $$$(5 - 2) \mod M = 3 \mod M = 3$$$
- $$$(6 - 3) \mod M = 3 \mod M = 3$$$
- $$$(7 - 4) \mod M = 3 \mod M = 3$$$
- $$$(8 - 5) \mod M = 3 \mod M = 3$$$
- $$$(9 - 6) \mod M = 3 \mod M = 3$$$
- $$$(10 - 7) \mod M = 3 \mod M = 3$$$
- $$$(11 - 8) \mod M = 3 \mod M = 3$$$
- $$$(12 - 9) \mod M = 3 \mod M = 3$$$
因此,$$$(0 + 998244345 + 998244345 + 998244345 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) \mod 10^9 + 7$$$ $$$=$$$ $$$2994733059 \mod 10^9 + 7$$$ $$$=$$$ $$$994733045$$$