题目描述

世界濒临破灭。Gleipse 正带领着$n$个魔法师试图拯救世界。

Gleipse 将$n$个魔法师排成一排。每个魔法师手上有两块水晶，每块水晶要么是红色的，要么是蓝色的。我们将第$i$个魔法师手上的两块水晶记作$a_i$，其意义为：

• $a_i = 0$：两块水晶都是红色的；

• $a_i = 1$：两块水晶，一块是红色的，一块是蓝色的；

• $a_i = 2$：两块水晶都是蓝色的。

现在 Gleipse 要收集所有人的水晶排成一行。他命令所有魔法师进行如下操作共$2n$次：

• 所有有水晶的魔法师同时选择自己手中的一块水晶，交给前面的一个魔法师。例如魔法师$i$将水晶交给魔法师$i - 1$。特殊的，魔法师$1$将水晶交给 Gleipse。

• Gleipse 将收到的水晶放在收集的水晶的队列末尾。

最终 Gleipse 将得到一个长度为$2n$的水晶队列。

因为$2n$块水晶足以阻止世界的破灭，所以 Gleipse 好奇所有可能出现的不同的水晶队列的数量。由于数量可能太多，所以 Gleipse 只要求答案对$998244353$取模的值。

输入格式

第一行一个整数$n$，表示魔法师的数量。 第二行共$n$个整数，表示$a_1,a_2,\cdots,a_n$。

输出格式

一行一个整数，表示答案对$998244353$取模的值。

数据范围

• 对于$30\%$的数据，$1 \leq n \leq 6$。
• 对于$60\%$的数据，$1 \leq n \leq 200$。
• 对于$100\%$的数据，$1 \leq n \leq 2 \times 10^3$，$0 \leq a_i \leq 2$。

样例数据

输入：

4
1 2 1 0

输出：

55