You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There is a hidden array $$$a$$$ of size $$$n$$$ consisting of only $$$1$$$ and $$$-1$$$. Let $$$p$$$ be the prefix sums of array $$$a$$$. More formally, $$$p$$$ is an array of length $$$n$$$ defined as $$$p_i = a_1 + a_2 + \ldots + a_i$$$. Afterwards, array $$$p$$$ is sorted in non-decreasing order. For example, if $$$a = [1, -1, -1, 1, 1]$$$, then $$$p = [1, 0, -1, 0, 1]$$$ before sorting and $$$p = [-1, 0, 0, 1, 1]$$$ after sorting.

You are given the prefix sum array $$$p$$$ after sorting, but you do not know what array $$$a$$$ is. Your task is to count the number of initial arrays $$$a$$$ such that the above process results in the given sorted prefix sum array $$$p$$$. As this number can be large, you are only required to find it modulo $$$998\,244\,353$$$.

## Input Format
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the size of the hidden array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$|p_i| \le n$$$) — the $$$n$$$ prefix sums of $$$a$$$ sorted in non-decreasing order.

It is guaranteed that $$$p_1 \le p_2 \le \ldots \le p_n$$$.

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

## Output Format
For each test case, output the answer modulo $$$998\,244\,353$$$.

## Examples
```input
5
1
0
1
1
3
-1 1 2
5
-1 0 0 1 1
5
-4 -3 -3 -2 -1
```
```output
0
1
0
3
1
```

## Note
In the first two test cases, the only possible arrays $$$a$$$ for $$$n = 1$$$ are $$$a = [1]$$$ and $$$a = [-1]$$$. Their respective sorted prefix sum arrays $$$p$$$ are $$$p = [1]$$$ and $$$p = [-1]$$$. Hence, there is no array $$$a$$$ that can result in the sorted prefix sum array $$$p = [0]$$$ and there is exactly $$$1$$$ array $$$a$$$ that can result in the sorted prefix sum array $$$p = [1]$$$.

In the third test case, it can be proven that there is no array $$$a$$$ that could result in the sorted prefix sum array $$$p = [-1, 1, 2]$$$.

In the fourth test case, the $$$3$$$ possible arrays $$$a$$$ that could result in the sorted prefix sum array $$$p = [-1, 0, 0, 1, 1]$$$ are:

- $$$a = [1, -1, 1, -1, -1]$$$. The prefix sum array before sorting is $$$p = [1, 0, 1, 0, -1]$$$, which after sorting gives $$$p = [-1, 0, 0, 1, 1]$$$.
- $$$a = [1, -1, -1, 1, 1]$$$. The prefix sum array before sorting is $$$p = [1, 0, -1, 0, 1]$$$, which after sorting gives $$$p = [-1, 0, 0, 1, 1]$$$.
- $$$a = [-1, 1, 1, -1, 1]$$$. The prefix sum array before sorting is $$$p = [-1, 0, 1, 0, 1]$$$, which after sorting gives $$$p = [-1, 0, 0, 1, 1]$$$.

For the fifth test case, the only possible array $$$a$$$ that could result in the sorted prefix sum array $$$p = [-4, -3, -3, -2, -1]$$$ is $$$a = [-1, -1, -1, -1, 1]$$$.

Now solve the problem and return the code.