7201: BZOJ3201：战斗力

  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个英雄时的战斗力。          

输入格式

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

输出格式

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

样例输入

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

提示

对于第一个样例，Tar可能的三种战斗力分别是(0,1),(1,0),(0,0)。
对于第二个样例，Tar的九个英雄战斗力都可能是0或1，根据乘法原理共有2^9=512种可能。
数据范围
100%的数据满足：N<=1000，0<=战斗力<=10^9，T<=5，Σ(N)<=4000
 

题目来源

没有写明来源