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