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

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

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

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

Примеры
Входные данные
3
Выходные данные
0
Входные данные
12
Выходные данные
994733045
Входные данные
21
Выходные данные
978932159
Входные данные
1000000000000
Выходные данные
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$$$