D. Permutation Blackholetime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputFor a permutation $$$p_1, p_2, \ldots, p_n$$$ of length $$$n$$$, the corresponding coloring sequence $$$s$$$ can be obtained by the following coloring process: Initially, there are $$$n$$$ white cells indexed from $$$1$$$ to $$$n$$$ from left to right. At second $$$0$$$, the score of each cell is $$$0$$$. At second $$$i$$$ ($$$1 \le i \le n$$$), If $$$i > 1$$$, find the nearest black cell to the cell $$$p_i$$$, and increase the score of that cell by $$$1$$$. In case there are multiple nearest black cells, choose the cell with the lowest index. Cell $$$y$$$ is called the nearest black cell to cell $$$x$$$ only if cell $$$y$$$ is black and there is no black cell $$$z$$$ satisfying $$$|x-z|<|x-y|$$$. Color the cell $$$p_i$$$ black. After all cells are colored black, denoting $$$s_i$$$ as the score of cell $$$i$$$ ($$$1 \le i \le n$$$), we get the coloring sequence $$$s$$$.You might want to read the notes for a better understanding.You are given an incomplete coloring sequence $$$s$$$, where some $$$s_i$$$ are already fixed, while others are not yet determined. Count how many different permutations $$$p$$$ can produce this coloring sequence. Since the answer may be large, you need to output it modulo $$$998\,244\,353$$$.InputEach 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. For each test case, the first line contains an integer $$$n$$$ ($$$2 \leq n \leq 100$$$).The second line contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_n$$$ ($$$-1 \leq s_i \leq n-1$$$). Here, $$$s_i=-1$$$ means $$$s_i$$$ has not been determined. And $$$s_i \neq -1$$$ means $$$s_i$$$ has already been fixed.It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^4$$$.OutputFor each test case, output the total of different permutations $$$p_1, p_2, \ldots, p_n$$$ that can produce the coloring sequence, modulo $$$998\,244\,353$$$.ExampleInput93-1 -1 13-1 -1 -14-1 2 -1 04-1 0 1 -15-1 3 -1 0 -154 4 4 4 451 0 1 2 06-1 1 -1 -1 3 013-1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1Output2 6 4 3 8 0 4 10 867303072 NoteIn the first test case, $$$p=[3,1,2]$$$ and $$$p=[3,2,1]$$$ can produce the coloring sequence $$$s=[-1,-1,1]$$$.For $$$p=[3,1,2]$$$, the coloring process is shown as the following picture. The grid at seconds $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ respectively when $$$p=[3,1,2]$$$. For $$$p=[3,2,1]$$$, the coloring process is shown as the following picture. The grid at seconds $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ respectively when $$$p=[3,2,1]$$$.