题目描述

Smart 来到了一个神秘的国度，它共有 \(N\) 个城市。传说在它的首都有一本秘籍，只要得到它就能变成强（\(S\)）者（\(B\)）。在找到了这个国家的地图之后，他发现地图经过长时间的磨损已经看不清了，他只能知道每个城市与几个城市相邻，并且在地图中边是双向的。已知这个国家的道路中不存在自环和重边，且不需要连通。现在 Smart 会告诉你每个城市相邻的城市个数，你需要求出共有多少种不同的地图，对 \(998244353\) 取模。

格式

输入格式

第一行一个整数 \(N\)。
第二行 \(N\) 个整数。第 \(i\) 个数 \(D_i\) 表示与第 \(i\) 个城市相邻的城市个数。

输出格式

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

样例1

样例输入1

4
2 1 1 2

样例输出1

2

限制

对于 \(20\%\) 的数据，满足 \(N≤10\)。
对于 \(50\%\) 的数据，满足 \(N≤200\)。
对于另外 \(10\%\) 的数据，满足 \(D_i=1\)。
对于另外 \(20\%\) 的数据，满足 \(D_i=2\)。
对于 \(100\%\) 的数据，满足 \(N≤2000,D_i∈\{1,2\}\)。