Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

G. Две сортировки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Целые числа от $$$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}$$$).

Выходные данные

Выведите одно целое число — ответ на задачу.

Примеры
Входные данные
3
Выходные данные
0
Входные данные
12
Выходные данные
2994733059
Входные данные
21
Выходные данные
11978932236
Входные данные
1000000000000
Выходные данные
499760084183610382682
Примечание

Число $$$\overline{x_1x_2 \ldots x_a}$$$ меньше числа $$$\overline{y_1y_2 \ldots y_b}$$$ в лексикографическом порядке если верно одно из двух условий:

  • либо $$$a \lt 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 \lt y_j$$$, то есть, в первой позиции, в которой числа отличаются, в первом числе стоит меньшая цифра.

Например, $$$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 = 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$$$.