题目描述

有一个长度为 $N$ 的数列 $A_i$。

你可以进行若干次，最多 $N-1$ 次操作，选择相邻的两个数，删去他们，并在原位置放上他们两个的和。

现在你需要求出可能产生的序列个数。

• $1 \le N \le 2 \times 10^5$
• $|A_i| \le 10^9$

答案对 $998244353$ 取余

输入格式

第一行输入一个整数 $N$

接下来一行输入 $N$ 个空格隔开的整数 $A_1,A_2,\cdots,A_N$

输出格式

求出可能产生的序列个数。

3
1 -1 1

4

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

321

提示

• $1\ \leq\ N\ \leq\ 2\times\ 10^5$
• $|A_i|\ \leq\ 10^9$