CF1601F Two Sorts

将 $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}$）。

输出一个整数——所求的和。

当且仅当满足以下条件之一时，字符串 $a$ 字典序小于字符串 $b$： - $a$ 是 $b$ 的前缀且 $a \ne b$； - 在第一个不同的位置，$a$ 的字符比 $b$ 对应位置的字符更小。 例如： - $42$ 字典序小于 $6$，因为第一位不同且 $4 < 6$； - $42 < 420$，因为 $42$ 是 $420$ 的前缀。 设 $M = 998244353$。 第一个样例中，数组 $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$ - $(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 $