题意：

纯数题 1≤i≤n, fi=max{a1,a2,…,ai}; 1≤i≤n, gi=min{a1,a2,…,ai}; 1≤i≤n, hi=fi−gi. 数列a是一个排列，问多少种排列方式满足h数列。

题目：

DreamGrid has an interesting permutation of 1,2,…,n denoted by a1,a2,…,an. 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≤i≤n, fi=max{a1,a2,…,ai}; For each 1≤i≤n, gi=min{a1,a2,…,ai}; For each 1≤i≤n, hi=fi−gi. 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 109+7.

Input

The input contains multiple cases. The first line of the input contains a single integer T (1≤T≤20000), the number of cases.

For each case, the first line of the input contains a single integer n (1≤n≤105), the length of the permutation as well as the sequences. The second line contains n integers h1,h2,…,hn (1≤i≤n,0≤hi≤109).

It’s guaranteed that the sum of n over all cases does not exceed 2⋅106.

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 109+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.

分析：

AC代码：

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef long long ll; const int M=1e5+10; const int mod=1e9+7; int t,n; ll ans,num; int a[M]; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); ans=1,num=0; if(a[1]!=0) { printf("0\n"); continue; } for(int i=2; i<=n; i++) { if(a[i]<a[i-1]||a[i]>=n||a[i]<0) { ans=0; break; }if(a[i]>a[i-1])//h[i] > h[i-1] ，那么比如0 3，说明第一个数和第二个数相差3，那么就找来一组数据x，y，放在这两个位置上，有两种顺序； { num+=a[i]-a[i-1]-1; ans*=2; ans%=mod; } else if(a[i]==a[i-1])//h[i] == h[i-1], 这种情况说明，新加上去的数，不影响前面的绝对差值，也就是加上的数处于差值范围内的任意一个数，这个差值是前面任意两个数之间的差值之和；统计出每种情况的数量，乘积就是总的方案书； { ans*=num; ans%=mod; num--; } } printf("%lld\n",ans); } return 0; }