蛋糕

小 L 送给了梓一块巨大的蛋糕。这个蛋糕可以用一个不降的长度为 $n$ 的序列 $a$ 表示。

每天，梓可以选择如下的一种吃法：

• 选择一个 $1\le i\le n$，进行操作 $a_i:=a_i-2$。
• 选择 $1\le i<n$ 满足 $a_i=a_{i+1}$，进行操作 $a_i:=a_i-1$，$a_{i+1}:=a_{i+1}-1$。

注意，需要保证每吃一次后，$a$ 仍然保持不降，且所有 $a$ 非负。请你告诉小 L，有多少种不同的吃法，使得最终所有 $a_i=0$。答案对 $998244353$ 取模。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$。

输出格式

第一行一个正整数表示答案。

样例

ex_cake0.in
2
3 3
ex_cake0.out
3
ex_cake1.in
6
2 2 3 5 6 6
ex_cake1.out
99792
ex_cake2.in
6
1 2 3 4 5 6
ex_cake2.out
0

ex_cake3.in/out见下发文件

数据范围

对于所有测试点，满足 $1\le n\le 1000$，$1\le a_i\le 1000$。对于一个 Subtask，如果你判断对了是否有解（即在答案 $=0$ 时输出了 $0$，否则输出了任意 $>0$ 且 $<10^9+7$ 的整数），那么你将获得其 $40\%$ 的分数。如果你在答案 $>0$ 时你的答案完全正确，那么将获得剩下 $60\%$ 的分数。保证有解时答案不为 $10^9+7$ 的倍数。

Subtask1 (25 pts): $n,a_i\le 8$。

Subtask2 (20 pts): $a_i=a_1$。

Subtask3 (55 pts): $n\le 1000$。