L. Best or Worst

George dreamt about an unusual permutation $p_1, p_2, \ldots, p_n$.

A permutation is considered unusual if, for each element $p_i$, exactly one of the following conditions is true:

1. $p_i=min(p_1,p_2,\ldots,p_i)$
2. $p_i=max(p_1,p_2,\ldots,p_i)$

For example, $[1]$, $[2,1,3,4]$ and $[1,2,3,4,5]$ are unusual, while $[3,1,2]$ and $[3,2,5,4,1]$ are not.

Unfortunately, after waking up, George remembers only some of the elements from $p$. As such, he now wonders how many unusual permutations containing the remaining numbers exist.

Since the answer can be very large, George only wants to know its remainder modulo $10^9+7$.

Input

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 2\cdot 10^4$) — the number of testcases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in the permutation.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le n$). If $a_i=0$, then George forgot the value of $p_i$. Otherwise, George knows that $p_i$ must be equal to $a_i$. It is guaranteed that there are no two indices $1 \le i \lt j \le n$ for which $0 \neq a_i=a_j$.

It is guaranteed that the sum of $n$ across all testcases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer, denoting the number of unusual permutations containing the remaining numbers. Since the answer can be very large, print its remainder modulo $10^9+7$.

Example

stdin

4
4
2 0 0 4
3
3 1 2
5
0 0 0 4 0
1
0

stdout

2
0
4
1

Note

In the first testcase, there are two possible permutations: $[2,1,3,4]$ and $[2,3,1,4]$, both of which are unusual.

In the second testcase, the only possible permutation is $[3,1,2]$, which is not unusual.

In the third testcase, the $4$ unusual permutations are $[1,2,3,4,5]$, $[2,1,3,4,5]$, $[2,3,1,4,5]$ and $[3,2,1,4,5]$.

In the fourth testcase, the only possible permutation is $[1]$, which is unusual.