题目描述

穿过了沙漠, 小 W 来到了一个神秘的国度, 它共有 $N$ 个城市。

传说在它的首都有一本秘籍, 只要得到它就能变成强（毒）者（瘤)。在找到了这个国家的地图之后, 他发现地图经过长时间的磨损已经看不清了, 他只能知道每个城市与几个城市相邻, 并且在地图中边是双向的。

已知这个国家的道路中不存在自环和重边, 且不需要连通。

现在小 $W$ 会告诉你每个城市相邻的城市个数, 你需要求出共有多少种不同的地图, 对 $998244353$ 取模。

输入格式

从文件 map.in 中读入数据。

第一行一个整数 $N$ 。

第二行 N 个整数。第 i 个数 $\mathrm{D}_{\mathrm{i}}$ 表示与第 i 个城市相邻的城市个数。

输出格式

输出到文件 map.out 中。

一行一个整数表示不同的地图数量对 $998244353$ 取模后的结果。

样例 1

4
2 1 1 2

2

样例 2

见下发文件 map.in。

见下发文件 map.out。

【数据范围】

对于 $20 \%$ 的数据, 满足 $N \leqslant 10$ 。

对于 $50 \%$ 的数据, 满足 $\mathrm{N} \leqslant 200$ 。

对于另外 $10 \%$ 的数据, 满足 $D_{i}=1$ 。

对于另外 $20 \%$ 的数据, 满足 $D_{i}=2$ 。

对于 $100 \%$ 的数据, 满足 $N \leqslant 2000, \underline{D}_{\mathbf{i}} \in\{1,2\}$ 。