不同的数组

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

题目描述

给定一个包含 $n$ 个整数的数组 $a$。

你需要依次对数组执行 $n-2$ 次操作。在第 $i$ 次操作（$1\le i\le n-2$）中，你可以选择以下两种方式之一：

• 将当前的 $a_{i+1}$ 加到 $a_i$ 上，并从 $a_{i+2}$ 中减去 $a_{i+1}$；
• 将当前的 $a_{i+1}$ 加到 $a_{i+2}$ 上，并从 $a_i$ 中减去 $a_{i+1}$。

也就是说，你需要将 $a_{i+1}$ 加到它的一个相邻元素上，并从另一个相邻元素中减去 $a_{i+1}$。每一步都使用执行该步之前数组中的当前值。

例如，从数组 $[1,2,3,4,5]$ 出发，可以进行如下操作：

• 从 $a_3$ 中减去 $2$，并将 $2$ 加到 $a_1$ 上，数组变为 $[3,2,1,4,5]$；
• 从 $a_2$ 中减去 $1$，并将 $1$ 加到 $a_4$ 上，数组变为 $[3,1,1,5,5]$；
• 从 $a_3$ 中减去 $5$，并将 $5$ 加到 $a_5$ 上，数组变为 $[3,1,-4,5,10]$。

如果一个数组能通过上述操作序列从 $a$ 得到，则称它为一个可达数组。求不同可达数组的数量。答案可能很大，请对 $998244353$ 取模。

输入格式

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

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示不同可达数组的数量对 $998244353$ 取模后的结果。

样例输入 1

4
1 1 1 1

样例输出 1

3

样例输入 2

5
1 2 3 5 0

样例输出 2

7

数据范围

对于所有测试数据，$3\le n\le 300$，$0\le a_i\le 300$。