L. Best or Worst

Time limit: 1s Memory limit: 256MB Input: Output:

George dreamt about an unusual permutation p1,p2,,pnp_1, p_2, \ldots, p_n.

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

  1. pi=min(p1,p2,,pi)p_i=min(p_1,p_2,\ldots,p_i)
  2. pi=max(p1,p2,,pi)p_i=max(p_1,p_2,\ldots,p_i)

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

Unfortunately, after waking up, George remembers only some of the elements from pp. 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 109+710^9+7.

Input

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

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

The second line of each test case contains nn integers a1,a2,,ana_1,a_2,\ldots,a_n (0ain0 \le a_i \le n). If ai=0a_i=0, then George forgot the value of pip_i. Otherwise, George knows that pip_i must be equal to aia_i. It is guaranteed that there are no two indices 1i<jn1 \le i \lt j \le n for which 0ai=aj0 \neq a_i=a_j.

It is guaranteed that the sum of nn across all testcases does not exceed 21052 \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 109+710^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][2,1,3,4] and [2,3,1,4][2,3,1,4], both of which are unusual.

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

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

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

Log in or sign up to be able to send submissions!