UOJ Logo Universal Online Judge

UOJ

附件下载 统计

最终,你以语文作文跑题结束了你的高考生涯,你只能回去搞OI了。

这就是你的宿命吗?

每个人都有自己的宿命,可以用一个次数不超过 n 的多项式 f(x)=k=0nakxk 来描述,其中 a0,,an 都是整数。假设你一共参加了 n+1 次影响你人生的考试,那么每一次考试的排名分别为 f(0),f(1),,f(n)

n+1 个正整数 c0,c1,,cn,如果对于每个 0in 均满足 1f(i)ci,那么就称这个宿命多项式为成功的。

现在给你 nc0,c1,,cn,求有多少个成功的宿命多项式。你只用输出答案对 9982443537×17×223+1,一个质数)取模后的值。

输入格式

第一行一个正整数 q,表示有 q 组询问。

接下来 q 行,每行表示一组询问。第一个数为正整数 n,后面跟着 n+1 个正整数 c0,c1,,cn,整数间均用一个空格分隔。

输出格式

对每组询问输出一行,表示相应的答案。

样例一

input

4
1 2 5
1 12345 67890
2 1 2 3
2 123 456 789

output

10
838102050
4
22126944

explanation

对于样例一的第 3 个询问,4 个成功的宿命多项式分别为:

  1. f(x)=1
  2. f(x)=x+1
  3. f(x)=x2+2x+1
  4. f(x)=x2x+1

样例二

input

2
4 3 3 3 3 3
4 10000 20000 30000 40000 50000

output

3
68284084

样例三

input

1
6 192837465 123456789 987654321 147258369 963852741 543219876 987651234

output

470636264

限制与约定

对于所有数据,q101c0,,cn109

测试点编号 n的规模 特殊限制
1n1
2n2c0,,cn105
3
4n3
5n4
6
7n5
8
9n6q=1
10

时间限制:1s

空间限制:256MB

下载

样例数据下载