题目描述

世界濒临破灭。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$ 取模的值。

4
1 2 1 0

55

数据范围

• 对于 $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$。