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

Есть неизвестный массив $$$a$$$ длины $$$n$$$, состоящий только из $$$1$$$ и $$$-1$$$. Пусть $$$p$$$ — массив префиксных сумм массива $$$a$$$. Более формально, $$$p$$$ — это массив длины $$$n$$$, в котором $$$p_i = a_1 + a_2 + \ldots + a_i$$$. После этого массив $$$p$$$ сортируется в неубывающем порядке. Например, если $$$a = [1, -1, -1, 1, 1]$$$, то $$$p = [1, 0, -1, 0, 1]$$$ до сортировки и $$$p = [-1, 0, 0, 1, 1]$$$ после сортировки.

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

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5000$$$) — длину неизвестного массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$|p_i| \le n$$$) — $$$n$$$ префиксных сумм массива $$$a$$$, отсортированных в порядке неубывания.

Гарантируется, что $$$p_1 \le p_2 \le \ldots \le p_n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.

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

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

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

В первых двух наборах входных данных единственными возможными массивами $$$a$$$ для $$$n = 1$$$ являются $$$a = [1]$$$ и $$$a = [-1]$$$. Соответствующие им отсортированные массивы префиксных сумм $$$p$$$ — $$$p = [1]$$$ и $$$p = [-1]$$$. Следовательно, не существует массива $$$a$$$, который может привести к отсортированному массиву префиксных сумм $$$p = [0]$$$. Но существует ровно $$$1$$$ массив $$$a$$$, который может привести к отсортированному массиву префиксных сумм $$$p = [1]$$$.

В третьем наборе входных данных можно доказать, что не существует массива $$$a$$$, который мог бы привести к отсортированному массиву префиксных сумм $$$p = [-1, 1, 2]$$$.

В четвертом наборе входных данных существует $$$3$$$ возможных массива $$$a$$$, которые могут привести к отсортированному массиву префиксных сумм $$$p = [-1, 0, 0, 1, 1]$$$.

  • $$$a = [1, -1, 1, -1, -1]$$$. Массив префиксных сумм до сортировки равен $$$p = [1, 0, 1, 0, -1]$$$, а после сортировки $$$p = [-1, 0, 0, 1, 1]$$$.
  • $$$a = [1, -1, -1, 1, 1]$$$. Массив префиксных сумм до сортировки равен $$$p = [1, 0, -1, 0, 1]$$$, а после сортировки $$$p = [-1, 0, 0, 1, 1]$$$.
  • $$$a = [-1, 1, 1, -1, 1]$$$. Массив префиксных сумм до сортировки равен $$$p = [-1, 0, 1, 0, 1]$$$, а после сортировки $$$p = [-1, 0, 0, 1, 1]$$$.

Для пятого набора входных данных единственным возможным массивом $$$a$$$, который может привести к отсортированному массиву префиксных сумм $$$p = [-4, -3, -3, -2, -1]$$$, является $$$a = [-1, -1, -1, -1, 1]$$$.