406392: GYM102394 I Interesting Permutation

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

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

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

3
3
0 2 2
3
0 1 2
3
0 2 3

2
4
0

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.