Задача №114753. Две сортировки
Целые числа от \(1\) до \(n\) отсортировали по возрастанию в лексикографическом порядке, рассматривая их как строки, и получили массив \(a_i\).
Требуется найти сумму \(\sum_{i = 1}^n ((i - a_i) \mod 998244353)\), где \(x \mod y\) означает остаток от деления числа \(x\) на число \(y\) (этот остаток всегда неотрицателен и не превосходит \(y - 1\)).
Обратите внимание, что суммирование ведётся без взятия остатка, то есть остаток берётся только от соответствующих разностей. А также обратите внимание, что ответ может не помещаться в 64-битный тип данных.
В первой строке содержится одно целое число \(n\) (\(1 \leq n \leq 10^{12}\)).
Выведите одно целое число — ответ на задачу.
Число \(\overline{x_1x_2 \ldots x_a}\) меньше числа \(\overline{y_1y_2 \ldots y_b}\) в лексикографическом порядке если верно одно из двух условий:
- либо \(a < b\) и \(x_1 = y_1, \ldots, x_a = y_a\), то есть первое слово является нетривиальным префиксом второго;
- либо есть такая позиция \(1 \leq j \leq \min(a, b)\), что \(x_1 = y_1, \ldots, x_{j-1} = y_{j-1}\) и \(x_j < y_j\), то есть, в первой позиции, в которой числа отличаются, в первом числе стоит меньшая цифра.
Например, \(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 = 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 = 2994733059\).
3
0
12
2994733059
21
11978932236
1000000000000
499760084183610382682