配点 : $500$ 点

問題文

長さ $N$ の数列 $A$ が与えられます。 数列の長さが $2$ 以上のとき、隣接する二つの値を選び、それらを削除し、それらが元にあった位置にそれらの和を挿入するという操作を好きなだけ行えます。 $0$ 回以上の操作の後の数列として考えられるものは何通りあるか求め、$998244353$ で割ったあまりを出力してください。

制約

• $1 \leq N \leq 2\times 10^5$
• $|A_i| \leq 10^9$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

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

出力

答えを出力せよ。

3
1 -1 1

4

$0$ 回以上の操作の後の数列として考えられるのは以下の $4$ 通りです。

• ${1,-1,1}$
• ${1,0}$
• ${0,1}$
• ${1}$

10
377914575 -275478149 0 -444175904 719654053 -254224494 -123690081 377914575 -254224494 -21253655

321