Целые числа от \(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\).
Примечание
Строка \(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\)