Kcats

Problem Description

Notice：Don't output extra spaces at the end of one line. Let $p_1, p_2, \cdots, p_n$ be a permutation of length $n$, Dodo bird built an array $a$ of length $n$ where $a_i$ indicates the size of the monotonic stack got from $p_1, p_2, \cdots, p_i$. For instance, if $p$ is $3,1,4,5,6,2$, we add the elements in the permutation to the monotonic stack one by one, the changes of the monotonic stack is as follows:

So the corresponding array $a$ is $1,1,2,3,4,2$. Years later, Dodo bird found the array $a$, but the value in some positions cannot be recognized anymore. He wants to know how many permutations can possibly be the original permutation. As the answer can be very large, you only need to output the answer module $10^9+7$.

Input

The first line contains a number $T(1 \leq T \leq 100)$, indicating the number of test cases. Each test case contains two lines. The first line contains an integer $n(1 \leq n \leq 100)$, indicating the length of the permutation. The second line contains $n$ integers $a_1, a_2, \cdots, a_n(-1 \leq a_i \leq n, a_i \not= 0)$, indicating the array $a$. $a_i=-1$ represents that the value of this position cannot be recognized.

Output

$T$ lines, each line is an integer, indicating the answer module $10^9 + 7$.

Sample Input

5
6
1 1 2 3 4 2
3
1 2 3
3
-1 -1 -1
3
1 1 1
3
3 3 3

Sample Output

5
1
6
1
0

Source

2020 Multi-University Training Contest 7