\(n\) человек собрались, чтобы провести заседание жюри предстоящего соревнования, \(i\)-й член жюри придумал \(a_i\) задач, которыми он хочет поделиться с другими.
Сначала жюри выбирает порядок, которому они будут следовать при обсуждении задач. Пусть это будет перестановка \(p\) чисел от \(1\) до \(n\) (массив размера \(n\), в котором каждое число от \(1\) до \(n\) встречается ровно один раз).
Затем обсуждение происходит следующим образом:
- если у члена жюри \(p_1\) остались задачи, которые нужно рассказать, то он рассказывает одну задачу. В противном случае он будет пропущен.
- если у члена жюри \(p_2\) остались задачи, которые нужно рассказать, то он рассказывает одну задачу. В противном случае он будет пропущен.
- ...
- если у члена жюри \(p_n\) остались задачи, которые нужно рассказать, то он рассказывает одну задачу. В противном случае он будет пропущен.
- если остались члены жюри, которые еще не рассказали все свои задачи, то процесс повторяется с самого начала. В противном случае обсуждение заканчивается.
Перестановка \(p\) хорошая, если никто из членов жюри не будет рассказывать две или более задач подряд.
Подсчитайте количество хороших перестановок. Ответ может быть очень большим, поэтому выведите его по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество хороших перестановок, взятое по модулю \(998\,244\,353\).
Примечание
Объяснение первого примера:
Существуют две возможные перестановки, \(p = [1, 2]\) и \(p = [2, 1]\). Для \(p = [1, 2]\) процесс происходит следующим образом:
- первый член жюри рассказывает задачу;
- второй член жюри рассказывает задачу;
- у первого члена жюри не осталось задач, которые нужно было бы рассказать, поэтому он будет пропущен;
- второй член жюри рассказывает задачу.
Второй член жюри рассказал две задачи подряд, поэтому перестановка не является хорошей.
Для \(p = [2, 1]\) процесс происходит следующим образом:
- второй член жюри рассказывает задачу;
- первый член жюри рассказывает задачу;
- второй член жюри рассказывает задачу.
Эта перестановка является хорошей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 2
3
5 5 5
4
1 3 3 7
6
3 4 2 1 3 3
|
1
6
0
540
|