E. Counting Cute Arrays
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Let $$$[A_1, A_2, \ldots, A_n]$$$ be an array of $$$n$$$ positive integers. Define array $$$f(A)$$$ as followed:

For each integer $$$i$$$ from $$$1$$$ to $$$n$$$:

  • If there exists integer $$$j$$$ such that $$$j \lt i$$$ and $$$A_j \lt A_i$$$, $$$f(A)_i=\max\limits_{j \lt i,A_j \lt A_i} j$$$. That is, $$$f(A)_i$$$ is the index of the rightmost element before $$$i$$$ whose value is strictly smaller than $$$A_i$$$.
  • Otherwise $$$f(A)_i=0$$$.

We call the array $$$[P_1,P_2,\ldots,P_n]$$$ of non-negative integers a cute array if there exists an array $$$A$$$ such that $$$f(A)=P$$$.

Given a length $$$n$$$ array $$$X$$$ in which $$$-1\le X_i\le n$$$ holds for all $$$i$$$ from $$$1$$$ to $$$n$$$. Count the numbers of cute arrays $$$X'$$$ formed by replacing the $$$-1$$$s in $$$X$$$ with integers from $$$0$$$ to $$$n$$$. As the number can be very large, print it modulo $$$998\,244\,353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test cases contain an integer $$$n$$$ ($$$1\le n\le5000$$$) denoting the length of $$$X$$$.

The second line contain $$$n$$$ integers $$$X_1,X_2,\ldots,X_n$$$ ($$$-1\le X_i\le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test cases, output a single integer denoting the number of arrays $$$X'$$$ such that $$$X'$$$ is a cute array, modulo $$$998\,244\,353$$$.

Example
Input
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
Output
2
3
42
1
0
0
Note

For the first test case, only $$$[0,0,0]$$$ and $$$[0,0,2]$$$ are cute arrays among all possible $$$X'$$$. $$$[0,0,0]$$$ is a good cute array because $$$f([1,1,1])=[0,0,0]$$$, and $$$[0,0,2]$$$ is a good array because $$$f([1,1,2])=[0,0,2]$$$.

For the second test case, only $$$[0,1,1,0]$$$, $$$[0,1,1,1]$$$ and $$$[0,1,1,3]$$$ are cute arrays among all possible $$$X'$$$.