E. Подсчёт милых массивов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$[A_1, A_2, \ldots, A_n]$$$ — массив из $$$n$$$ целых положительных чисел. Определим массив $$$f(A)$$$ следующим образом:

Для каждого целого числа $$$i$$$ от $$$1$$$ до $$$n$$$:

  • Если существует целое число $$$j$$$, такое что $$$j \lt i$$$ и $$$A_j \lt A_i$$$, то $$$f(A)_i=\max\limits_{j \lt i,A_j \lt A_i} j$$$. То есть, $$$f(A)_i$$$ — это индекс самого правого элемента перед $$$i$$$, значение которого строго меньше $$$A_i$$$.
  • В противном случае $$$f(A)_i=0$$$.

Мы называем массив $$$[P_1,P_2,\ldots,P_n]$$$ из целых неотрицательных чисел милым массивом, если существует массив $$$A$$$, такой что $$$f(A)=P$$$.

Дан массив $$$X$$$ длины $$$n$$$, в котором для всех $$$i$$$ от $$$1$$$ до $$$n$$$ выполняется $$$-1\le X_i\le n$$$. Посчитайте количество милых массивов $$$X'$$$, образованных заменой $$$-1$$$ в $$$X$$$ на целые числа от $$$0$$$ до $$$n$$$. Поскольку число может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1\le n\le5000$$$), обозначающее длину $$$X$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$X_1,X_2,\ldots,X_n$$$ ($$$-1\le X_i\le n$$$).

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

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

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

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

Для первого набора входных данных только $$$[0,0,0]$$$ и $$$[0,0,2]$$$ являются милыми массивами среди всех возможных $$$X'$$$. $$$[0,0,0]$$$ — хороший милый массив, потому что $$$f([1,1,1])=[0,0,0]$$$, а $$$[0,0,2]$$$ — хороший массив, потому что $$$f([1,1,2])=[0,0,2]$$$.

Для второго набора входных данных только $$$[0,1,1,0]$$$, $$$[0,1,1,1]$$$ и $$$[0,1,1,3]$$$ являются милыми массивами среди всех возможных $$$X'$$$.