/ WHOJ / 题库 /

地图

地图

题目描述

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

格式

输入格式

第一行一个整数 NN
第二行 NN 个整数。第 ii 个数 DiD_i 表示与第 ii 个城市相邻的城市个数。

输出格式

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

样例1

样例输入1

4
2 1 1 2

样例输出1

限制

对于 20%20\% 的数据,满足 N10N≤10
对于 50%50\% 的数据,满足 N200N≤200
对于另外 10%10\% 的数据,满足 Di=1D_i=1
对于另外 20%20\% 的数据,满足 Di=2D_i=2
对于 100%100\% 的数据,满足 N2000,Di{1,2}N≤2000,D_i∈\{1,2\}