Permutation Counting

Problem Description

For a given permutation $a_1, a_2, \cdots, a_n$ of length $n$, we defined the neighbor sequence $b$ of $a$, the length of which is $n-1$, as following:

$$b_i= \begin{cases}0~~~a_i\text{ < } a_{i+1} \\ 1~~~a_i>a_{i+1}\end{cases} $$

For example, the neighbor sequence of permutation $1,2,3,6,4,5$ is $0,0,0,1,0$. Now we give you an integer $n$ and a sequence $b_1, b_2, \cdots, b_{n-1}$ of length $n-1$, you should calculate the number of permutations of length $n$ whose neighbor sequence equals to $b$. To avoid calculation of big number, you should output the answer module $10^9+7$.

Input

The first line contains one positive integer $T$ ($1\le T \le 50$), denoting the number of test cases. For each test case: The first line of the input contains one integer $n, (2 \le n \le 5000)$. The second line of the input contains $n - 1$ integer: $b_1, b_2, \cdots, b_{n - 1}$ There are no more than $20$ cases with $n > 300$.

Output

For each test case: Output one integer indicating the answer module $10^9 + 7$.

Sample Input

2
3
1 0
5
1 0 0 1

Sample Output

2
11

Source

2020 Multi-University Training Contest 10