Predilection

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定一个长度为 $N$ 的整数序列 $A$。当序列长度至少为 $2$ 时，可以进行任意多次如下操作：选择两个相邻元素，删除它们，并在原位置插入它们的和。

求经过零次或多次操作后，可能得到多少种不同的非空整数序列。答案对 $998244353$ 取模。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出一个整数，表示不同结果序列的数量对 $998244353$ 取模后的值。

样例输入 1

3
1 -1 1

样例输出 1

4

样例输入 2

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

样例输出 2

321

数据范围

对于全部数据，$1\le N\le2\times10^5$，$|A_i|\le10^9$。