D. Перестановочная черная дыра
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для перестановки $$$p_1, p_2, \ldots, p_n$$$ длины $$$n$$$ соответствующая покрасочная последовательность $$$s$$$ может быть получена следующим процессом раскраски:

  • Изначально есть $$$n$$$ белых ячеек, пронумерованных от $$$1$$$ до $$$n$$$. На секунде $$$0$$$ счет каждой ячейки равен $$$0$$$.

  • На секунде $$$i$$$ ($$$1 \le i \le n$$$),
    • Если $$$i \gt 1$$$, найдите ближайшую к ячейке $$$p_i$$$ черную ячейку и увеличьте счет этой ячейки на $$$1$$$. В случае, если есть несколько ближайших черных ячеек, выберите ячейку с наименьшим номером. Ячейка $$$y$$$ называется ближайшей черной ячейкой к ячейке $$$x$$$, только если ячейка $$$y$$$ черная и нет черной ячейки $$$z$$$, удовлетворяющей условию $$$|x-z| \lt |x-y|$$$.
    • Покрасьте ячейку $$$p_i$$$ в черный цвет.

После того как все ячейки покрашены в черный цвет, обозначим $$$s_i$$$ как счет ячейки $$$i$$$ ($$$1 \le i \le n$$$). Это и будет покрасочной последовательностью $$$s$$$.

Для лучшего понимания условия обратитесь к примечаниям к примеру.

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

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

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

Для каждого набора входных данных первая строка содержит целое число $$$n$$$ ($$$2 \leq n \leq 100$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$s_1, s_2, \ldots, s_n$$$ ($$$-1 \leq s_i \leq n-1$$$). Здесь $$$s_i=-1$$$ означает, что $$$s_i$$$ не было определено. А $$$s_i \neq -1$$$ означает, что $$$s_i$$$ уже зафиксировано.

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

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

Для каждого набора входных данных выведите общее количество различных перестановок $$$p_1, p_2, \ldots, p_n$$$, которые могут привести к данной покрасочной последовательности, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
9
3
-1 -1 1
3
-1 -1 -1
4
-1 2 -1 0
4
-1 0 1 -1
5
-1 3 -1 0 -1
5
4 4 4 4 4
5
1 0 1 2 0
6
-1 1 -1 -1 3 0
13
-1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1
Выходные данные
2
6
4
3
8
0
4
10
867303072
Примечание

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

Для $$$p=[3,1,2]$$$ процесс раскраски показан на следующем рисунке.

Сетка на секундах $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ соответственно, при $$$p=[3,1,2]$$$.

Для $$$p=[3,2,1]$$$ процесс раскраски показан на следующем рисунке.

Сетка на секундах $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ соответственно, при $$$p=[3,2,1]$$$.