题目描述

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$ 行，每行一个数表示答案，答案对 $10^9 + 7$ 取模。

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 \leq 1000$，$0 \leq \text{战斗力} \leq 10^9$，$T \leq 5$，$\sum{n}\leq4000$。