L. Best Or Worst
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

G 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, G 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, G 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 G forgot the value of $$$p_i$$$. Otherwise, G 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
Input
4
4
2 0 0 4
3
3 1 2
5
0 0 0 4 0
1
0
Output
2
0
4
1
Note

The bolded numbers denote the elements that G remembered:

  • In the first testcase, there are two possible permutations: $$$[\textbf{2},1,3,\textbf{4}]$$$ and $$$[\textbf{2},3,1,\textbf{4}]$$$, both of which are unusual.
  • In the second testcase, the only possible permutation is $$$[\textbf{3},\textbf{1},\textbf{2}]$$$, which is not unusual.
  • In the third testcase, the $$$4$$$ unusual permutations are $$$[1,2,3,\textbf{4},5]$$$, $$$[2,1,3,\textbf{4},5]$$$, $$$[2,3,1,\textbf{4},5]$$$ and $$$[3,2,1,\textbf{4},5]$$$.
  • In the fourth testcase, the only possible permutation is $$$[1]$$$, which is unusual.