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

这就是你的宿命吗？

每个人都有自己的宿命，可以用一个次数不超过 $n$ 的多项式 $f(x)=\sum _{k=0}^n{a}_k{x}^k$ 来描述，其中 $a_0,\dots ,a_n$ 都是整数。假设你一共参加了 $n+1$ 次影响你人生的考试，那么每一次考试的排名分别为 $f(0),f(1),\dots ,f(n)$。

有 $n+1$ 个正整数 $c_0,c_1,\dots ,c_n$，如果对于每个 $0\le i\le n$ 均满足 $1\le f(i)\le c_i$，那么就称这个宿命多项式为成功的。

现在给你 $n$ 和 $c_0,c_1,\dots ,c_n$，求有多少个成功的宿命多项式。你只用输出答案对 $998244353$（$7\times 17\times 2^{23}+1$，一个质数）取模后的值。

输入格式

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

接下来 $q$ 行，每行表示一组询问。第一个数为正整数 $n$，后面跟着 $n+1$ 个正整数 $c_0,c_1,\dots ,c_n$，整数间均用一个空格分隔。

输出格式

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

样例一

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)=-x^2+2x+1$
4. $f(x)=x^2-x+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

限制与约定

对于所有数据，$q\le 10$，$1\le c_0,\dots ,c_n\le {10}^9$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载