На Moscow Workshops ICPC команды получают воздушные шарики за каждую задачу, которую они решили первыми. Команда MSU Red Panda получила так много шариков, что они не знали, что с ними делать. Тогда они придумали о них задачу.
Есть несколько шариков, всего не более \(10^6\), каждый покрашен в один из \(k\) цветов. Мы можем делать следующую операцию: выбрать \(k-1\) шариков \(k-1\) различных цветов, и перекрасить их все в оставшийся цвет. Мы можем выполнять данную операцию любое конечное число раз (в частности, мы можем выполнить очередную операцию только если существует по крайней мере \(k-1\) различных цветов среди шариков в данный момент).
Сколько различных конфигураций шариков мы можем получить? Играет роль только количество шариков каждого цвета, конфигурации, отличающиеся только порядком шариков, считаются одинаковыми. Так как это число может быть очень большим, выведите его по модулю \(998244353\).
Выходные данные
Выведите число возможных конфигураций по модулю \(998244353\).
Примечание
В первом примерe существуют \(3\) конфигурации которые мы можем получить: \([0, 1, 2]\), \([2, 0, 1]\), \([1, 2, 0]\).
В втором примере мы можем применить операцию не более одного раза, и достижимыми являются : \([1, 1, 1, 1]\), \([0, 0, 0, 4]\), \([0, 0, 4, 0]\), \([0, 4, 0, 0]\), \([4, 0, 0, 0]\).
В третьем примере мы не можем применить ни одной операции, поэтому единственная достижимая конфигурация - начальная.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 1 2
|
3
|
|
2
|
4
1 1 1 1
|
5
|
|
3
|
5
0 0 1 2 3
|
1
|
|
4
|
3
2 2 8
|
31
|