logo AlgoBeat OnlineJudge
登录 注册

#103201. [BZOJ 3201] 战斗力

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

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

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

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

Tar:……

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

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

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

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

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

输入格式

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

输出格式

行,每行一个数表示答案,答案对 取模。

样例

样例输入 #1

4
2 1 2
9 2 2 2 2 2 2 2 2 2
3 5 1 2
5 3 14159 2653589 7 932

样例输出 #1

3
512
34
353127147

样例说明

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

对于第二个样例,Tar 的九个英雄战斗力都可能是 ,根据乘法原理共有 种可能。

数据范围与提示

  • 的数据满足: