#1074. 战斗力

战斗力

Description

Tar的同学是LOL大神,但是Tar的某些英雄比他的同学玩得好。每次Tar试图用他某个英雄玩得比同学好这个事情说服他的同学叫他大神时,就会发生这样的蛋疼对话:

Tar:“我提莫玩得比你好,快叫我大神。”

同学:“你提莫还没我艾希玩得好呢。”

Tar:“你艾希玩得还没我安妮好啊。”

同学:“你安妮还没我盖伦玩得好啊。”

Tar:……

讨论到最后Tar发现,按照他同学的奇怪算法,他的同学战斗力的确会比他高一点点。因为每次他随便举出一个英雄X,他的同学就能举出一个英雄X’(X’不一定和X是一个英雄),而他同学使用英雄X’的战斗力的确高于他使用英雄X的战斗力。而且在tar选择的英雄X不同的时候,他的同学选择的英雄X’也是不同的,

换句话说,如果把他们两个人各个英雄的战斗力画在二分图的两侧,那么这个二分图存在一个完全匹配,每个匹配两端,Tar对应英雄的战斗力都严格低于他同学对应英雄的战斗力。

Tar又赢了几局LOL,一些英雄的战斗力数值提高了,可是他发现这几次下来,通过刚才的奇怪算法,他的同学的战斗力依然能够比他高。

于是Tar现在在考虑的问题就是:在他同学战斗力不变的情况下,Tar到底有多少种战斗力组合会被同学完爆。

我们假设LOL这个游戏一共有N个英雄,每个玩家的战斗力由N个非负整数刻画,第I个数值表示玩家使用第I个英雄时的战斗力。

Format

Input

多组数据。第一行是数据组数T。

接下来T行每行表示一组数据。每组数据以N开头,后面N个整数表示Tar同学的战斗力。

Output

T行,每行一个数表示答案,模1000000007。

Samples

4
2 1 2
9 2 2 2 2 2 2 2 2 2
3 5 1 2
5 3 14159 2653589 7 932
3
512
34
353127147

Limitation

对于第一个样例,Tar可能的三种战斗力分别是(0,1),(1,0),(0,0)。

对于第二个样例,Tar的九个英雄战斗力都可能是0或1,根据乘法原理共有2^9=512种可能。

数据范围

100%的数据满足:N<=1000,0<=战斗力<=10^9,T<=5,Σ(N)<=4000