给定一个整数 $n$ 和一个多项式 $P(x) = a_0 + a_1x + \dots + a_nx^n$，其中 $a_0, a_1, \dots, a_n$ 均为非负整数。

考虑级数 $S = \sum_{m=0}^{\infty} \frac{P(m)}{m!}$。可以证明 $S$ 是良定义的，且我们总能将其表示为 $S = pe$，其中 $p$ 是一个非负整数，$e = \sum_{m=0}^{\infty} \frac{1}{m!} \approx 2.71828$ 是欧拉数。你需要计算 $p \pmod{998244353}$。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 100$)。 每个测试用例的描述如下： 第一行包含一个整数 $n$ ($0 \le n \le 10^5$)。 第二行包含 $n + 1$ 个用空格分隔的整数 $a_0, a_1, \dots, a_n$ ($0 \le a_i < 998244353$)。 保证对于至多 4 个测试用例，$n > 1000$。

输出格式

对于每个测试用例，输出 $p \pmod{998244353}$，其中 $p$ 的定义如题所述。

样例

输入 1

2
1
1 2
5
1 1 4 5 1 4

输出 1

3
258