给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。
您必须对此数组执行 $$$n-2$$$ 操作序列:
- 在第一次操作期间,您可以将 $$$a_2$$$ 添加到 $$$a_1$$$ 并从 $$$a_3$$$ 中减去 $$$a_2$$$,或者将 $$$a_2$$$ 添加到 $$$a_3$$$ 并从 $$$a_1$$$ 中减去 $$$a_2$$$;
- 在第二次操作期间,您可以将 $$$a_3$$$ 添加到 $$$a_2$$$ 并从 $$$a_4$$$ 中减去 $$$a_3$$$,或者将 $$$a_3$$$ 添加到 $$$a_4$$$ 并从 $$$a_2$$$ 中减去 $$$a_3$$$;
- ...
- 在最后一个操作中,您可以将 $$$a_{n-1}$$$ 添加到 $$$a_{n-2}$$$ 并从 $$$a_n$$$ 中减去 $$$a_{n-1}$$$,或者将 $$$a_{n-1}$$$ 添加到 $$$a_n$$$ 并从 $$$a_{n-1}$$$ 中减去 $$$a_{n-1}$$$ $$$a_{n-2}$$$。
因此,在第 $$$i$$$ 操作期间,将 $$$a_{i+1}$$$ 的值添加到它的一个邻居中,并从另一个邻居中减去它。
例如,如果您有数组 $$$[1, 2, 3, 4, 5]$$$,则可能的操作序列之一是:
- 从 $$$a_3$$$ 中减去 $$$2$$$ 并将其添加到 $$$a_1$$$ 中,因此数组变为 $$$[3, 2, 1, 4, 5]$$$;
- 从 $$$a_2$$$ 中减去 $$$1$$$ 并将其添加到 $$$a_4$$$,因此数组变为 $$$[3, 1, 1, 5, 5]$$$;
- 从 $$$a_3$$$ 中减去 $$$5$$$ 并将其添加到 $$$a_5$$$,因此数组变为 $$$[3, 1, -4, 5, 10]$$$。
因此,结果数组是 $$$[3, 1, -4, 5, 10]$$$。
如果可以通过对 $$$a$$$ 执行上述操作序列来获取数组,则该数组是可达的。您必须计算可到达数组的数量,并以 $$$998244353$$$ 为模打印它。
输入
第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 300$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 300$$$)。
输出
打印一个整数 — 可到达数组的数量。由于答案可能非常大,因此打印其对 $$$998244353$$$ 取模后的余数。
示例
输入 #1
4 1 1 1 1
输出 #1
3
输入 #2
5 1 2 3 5 0
输出 #2
7