E. Задача от Red Pandы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На Moscow Workshops ICPC команды получают воздушные шарики за каждую задачу, которую они решили первыми. Команда MSU Red Panda получила так много шариков, что они не знали, что с ними делать. Тогда они придумали о них задачу.

Есть несколько шариков, всего не более $$$10^6$$$, каждый покрашен в один из $$$k$$$ цветов. Мы можем делать следующую операцию: выбрать $$$k-1$$$ шариков $$$k-1$$$ различных цветов, и перекрасить их все в оставшийся цвет. Мы можем выполнять данную операцию любое конечное число раз (в частности, мы можем выполнить очередную операцию только если существует по крайней мере $$$k-1$$$ различных цветов среди шариков в данный момент).

Сколько различных конфигураций шариков мы можем получить? Играет роль только количество шариков каждого цвета, конфигурации, отличающиеся только порядком шариков, считаются одинаковыми. Так как это число может быть очень большим, выведите его по модулю $$$998244353$$$.

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

Первая строка содержит одно целое число $$$k$$$ ($$$2 \le k \le 10^5$$$) —количество цветов.

Вторая строка содержит $$$k$$$ целых чисел $$$a_1, a_2, \ldots, a_k$$$ ($$$0 \le a_i$$$) —начальную конфигурацию шариков. $$$a_i$$$ равно количеству шариков цвета $$$i$$$. Общее число шариков не превосходит $$$10^6$$$. Другими словами,

$$$a_1 + a_2 + a_3 + \ldots + a_k \le 10^6$$$.

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

Выведите число возможных конфигураций по модулю $$$998244353$$$.

Примеры
Входные данные
3
0 1 2
Выходные данные
3
Входные данные
4
1 1 1 1
Выходные данные
5
Входные данные
5
0 0 1 2 3
Выходные данные
1
Входные данные
3
2 2 8
Выходные данные
31
Примечание

В первом пример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]$$$.

В третьем примере мы не можем применить ни одной операции, поэтому единственная достижимая конфигурация - начальная.