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:

$$
\begin{equation}

b_i=

\begin{cases}

0 & a_i < a_{i + 1}\\
1 & a_i > a_{i + 1}
\end{cases}

\end{equation}
$$.

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$.

2
3
1 0
5
1 0 0 1

2
11