Задано два целых числа \(l\) и \(r\) (\(l \le r\)). Ваша задача — посчитать сумму чисел от \(l\) до \(r\) (включая \(l\) и \(r\)) таких, что каждое число содержит не более \(k\) различных цифр, и вывести эту сумму по модулю \(998244353\).
Например, если \(k = 1\), тогда вам необходимо посчитать все числа от \(l\) до \(r\) такие, что каждое число содержит только одинаковые цифры. Для \(l = 10, r = 50\) ответ равен \(11 + 22 + 33 + 44 = 110\).
Выходные данные
Выведите одно целое число — сумму чисел от \(l\) до \(r\) таких, что каждое число содержит не более \(k\) различных цифр, по модулю \(998244353\).
Примечание
В первом тестовом примере ответом является сумма чисел от \(l\) до \(r\), которая равна \(\frac{50 \cdot 51}{2} - \frac{9 \cdot 10}{2} = 1230\). Этот пример также разобран в условии задачи, но для \(k = 1\).
Во втором тестовом примере ответом является просто сумма чисел от \(l\) до \(r\), которая равна \(\frac{2345 \cdot 2346}{2} = 2750685\).
В третьем тестовом примере ответ равен \(101 + 110 + 111 + 112 + 113 + 114 + 115 + 116 + 117 + 118 + 119 + 121 + 122 + 131 + 133 + 141 + 144 + 151 = 2189\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 50 2
|
1230
|
|
2
|
1 2345 10
|
2750685
|
|
3
|
101 154 2
|
2189
|