最终，你以语文作文跑题结束了你的高考生涯，你只能回去搞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 \leq i \leq n$ 均满足 $1 \leq f(i) \leq 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 \leq 10$，$1 \leq c_0, \dots, c_n \leq 10^9$。

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载