CF1601F.Two Sorts

Integers from $1$ to $n$ (inclusive) were sorted lexicographically (considering integers as strings). As a result, array $a_1, a_2, \dots, a_n$ was obtained.

Calculate value of $(\sum_{i = 1}^n ((i - a_i) \mod 998244353)) \mod 10^9 + 7$.

$x \mod y$ here means the remainder after division $x$ by $y$. This remainder is always non-negative and doesn't exceed $y - 1$. For example, $5 \mod 3 = 2$, $(-1) \mod 6 = 5$.

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

The first line contains the single integer $n$ ($1 \leq n \leq 10^{12}$).

第一行包含一个整数 $n$（$1 \leq n \leq 10^{12}$）。

Print one integer — the required sum.

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

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a \ne b$;
• in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

For example, $42$ is lexicographically smaller than $6$, because they differ in the first digit, and $4 \lt 6$; $42 \lt 420$, because $42$ is a prefix of $420$.

Let's denote $998244353$ as $M$.

In the first example, array $a$ is equal to $[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$

As a result, $(0 + 0 + 0) \mod 10^9 + 7 = 0$

In the second example, array $a$ is equal to $[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$

As a result, $(0 + 998244345 + 998244345 + 998244345 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) \mod 10^9 + 7$ $=$ $2994733059 \mod 10^9 + 7$ $=$ $994733045$

字符串 $a$ 的字典序小于字符串 $b$，当且仅当满足以下条件之一：

• $a$ 是 $b$ 的前缀，但 $a \ne b$；
• 在 $a$ 与 $b$ 首次出现差异的位置上，$a$ 中的字符在字母表中位于 $b$ 中对应字符之前。

例如，$42$ 的字典序小于 $6$，因为它们在第一位数字处不同，且 $4 \lt 6$；$42 \lt 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$