C. Заседание жюри
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

$$$n$$$ человек собрались, чтобы провести заседание жюри предстоящего соревнования, $$$i$$$-й член жюри придумал $$$a_i$$$ задач, которыми он хочет поделиться с другими.

Сначала жюри выбирает порядок, которому они будут следовать при обсуждении задач. Пусть это будет перестановка $$$p$$$ чисел от $$$1$$$ до $$$n$$$ (массив размера $$$n$$$, в котором каждое число от $$$1$$$ до $$$n$$$ встречается ровно один раз).

Затем обсуждение происходит следующим образом:

  • если у члена жюри $$$p_1$$$ остались задачи, которые нужно рассказать, то он рассказывает одну задачу. В противном случае он будет пропущен.
  • если у члена жюри $$$p_2$$$ остались задачи, которые нужно рассказать, то он рассказывает одну задачу. В противном случае он будет пропущен.
  • ...
  • если у члена жюри $$$p_n$$$ остались задачи, которые нужно рассказать, то он рассказывает одну задачу. В противном случае он будет пропущен.
  • если остались члены жюри, которые еще не рассказали все свои задачи, то процесс повторяется с самого начала. В противном случае обсуждение заканчивается.

Перестановка $$$p$$$ хорошая, если никто из членов жюри не будет рассказывать две или более задач подряд.

Подсчитайте количество хороших перестановок. Ответ может быть очень большим, поэтому выведите его по модулю $$$998\,244\,353$$$.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — количество задач, которые придумал $$$i$$$-й член жюри.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — количество хороших перестановок, взятое по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4
2
1 2
3
5 5 5
4
1 3 3 7
6
3 4 2 1 3 3
Выходные данные
1
6
0
540
Примечание

Объяснение первого примера:

Существуют две возможные перестановки, $$$p = [1, 2]$$$ и $$$p = [2, 1]$$$. Для $$$p = [1, 2]$$$ процесс происходит следующим образом:

  1. первый член жюри рассказывает задачу;
  2. второй член жюри рассказывает задачу;
  3. у первого члена жюри не осталось задач, которые нужно было бы рассказать, поэтому он будет пропущен;
  4. второй член жюри рассказывает задачу.

Второй член жюри рассказал две задачи подряд, поэтому перестановка не является хорошей.

Для $$$p = [2, 1]$$$ процесс происходит следующим образом:

  1. второй член жюри рассказывает задачу;
  2. первый член жюри рассказывает задачу;
  3. второй член жюри рассказывает задачу.

Эта перестановка является хорошей.