I. Interesting Permutation
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

DreamGrid has an interesting permutation of $$$1, 2, \dots, n$$$ denoted by $$$a_1, a_2, \dots, a_n$$$. He generates three sequences $$$f$$$, $$$g$$$ and $$$h$$$, all of length $$$n$$$, according to the permutation $$$a$$$ in the way described below:

  • For each $$$1 \le i \le n$$$, $$$f_i = \max\{a_1, a_2, \dots, a_i \}$$$;
  • For each $$$1 \le i \le n$$$, $$$g_i = \min\{a_1, a_2, \dots, a_i \}$$$;
  • For each $$$1 \le i \le n$$$, $$$h_i = f_i - g_i$$$.

BaoBao has just found the sequence $$$h$$$ DreamGrid generates and decides to restore the original permutation. Given the sequence $$$h$$$, please help BaoBao calculate the number of different permutations that can generate the sequence $$$h$$$. As the answer may be quite large, print the answer modulo $$$10^9+7$$$.

Input

The input contains multiple cases. The first line of the input contains a single integer $$$T$$$ ($$$1\leq T\leq 20\,000$$$), the number of cases.

For each case, the first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the length of the permutation as well as the sequences. The second line contains $$$n$$$ integers $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le i \le n, 0 \le h_i \le 10^9$$$).

It's guaranteed that the sum of $$$n$$$ over all cases does not exceed $$$2\cdot 10^6$$$.

Output

For each case, print a single line containing a single integer, the number of different permutations that can generate the given sequence $$$h$$$. Don't forget to print the answer modulo $$$10^9+7$$$.

Example
Input
3
3
0 2 2
3
0 1 2
3
0 2 3
Output
2
4
0
Note

For the first sample case, permutations $$$\{1, 3, 2\}$$$ and $$$\{3, 1, 2\}$$$ can both generate the given sequence.

For the second sample case, permutations $$$\{1, 2, 3\}$$$, $$$\{2, 1, 3\}$$$, $$$\{2, 3, 1\}$$$ and $$$\{3, 2, 1\}$$$ can generate the given sequence.