問題文

数列 $(a_1,a_2,\ldots,a_n)$ に対して、$b_i=a_1+\cdots+a_i$ により定まる数列 $(b_1,b_2,\ldots,b_n)$ を累積和と呼ぶことにします。

長さ $N$ の数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。数列の長さが $1$ になるまで、以下の操作を繰り返します。

• 数列 $A$ を累積和で置き換える。その後、数列 $A$ の先頭の項を捨てる。

数列の長さが $1$ になったとき、その項を $998244353$ で割った余りを求めてください。

制約

• $1\le N\le 2\times 10^5$
• $0\le A_i< 998244353$
• 入力はすべて整数

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

出力

最後に改行してください。

サンプル

3
1 0 2

4

9
3 1 4 1 5 9 2 6 5

12784

2
900000000 800000000

701755647