B. Подсчет сеток
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
ParagonX9 - HyperioxX
⠀

У Алисы есть сетка размером $$$n \times n$$$. Изначально все ячейки окрашены в белый цвет. Алиса хочет покрасить некоторые ячейки в черный цвет, удовлетворяя определенным условиям.

Пусть $$$(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)$$$ — это ячейки, окрашенные в черный цвет. Вам дан массив $$$a$$$ размером $$$n$$$. Необходимо, чтобы выполнялись следующие условия:

  • Для каждой строки $$$k$$$ ($$$1 \le k \le n$$$) существует ровно $$$a_k$$$ индексов $$$i$$$ ($$$1 \le i \le m$$$), такие, что $$$x_i = k$$$. Другими словами, в строке $$$k$$$ должно быть $$$a_k$$$ черных ячеек.
  • Для каждого $$$k$$$ ($$$1 \le k \le n$$$) существует ровно один индекс $$$i$$$ такой, что $$$\max(x_i, y_i) = k$$$.
  • Для каждого $$$k$$$ ($$$1 \le k \le n$$$) существует ровно один индекс $$$i$$$ такой, что $$$\max(x_i, n + 1 - y_i) = k$$$.

Например, когда $$$a = [2, 2, 1, 0, 0]$$$, возможный набор черных ячеек — это $$$\{(1, 1), (2, 2), (3, 3), (2, 4), (1, 5)\}$$$. Это соответствует следующей сетке:

Сетка 5×5 с указанными черными ячейками.

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

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел — $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).

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

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

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

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

В первом наборе входных данных единственная допустимая сетка — это та, что указана в условии.

Во втором наборе входных данных единственная допустимая сетка описывается набором черных ячеек $$$\{(1, 1), (1, 2)\}$$$.

В третьем наборе входных данных нет допустимых сеток.