分数: 800 点
问题陈述
高桥即将组装一个人物模型,包括 N 称为零件的零件 1,部分 2,...,部分 N 和 N-1 连接组件。零件是可区分的,但连接组件则不可区分。
部分 i 有 d_i 孔,称为 Hole 1, 孔 2, ..., 孔 d_i,其中可以插入连接组件。零件上的这些孔是可区分的。 每个连接部件将插入不同部件的两个孔中,连接这两个部件。不可能将多个连接部件插入一个孔中。
当人物形象具有以下属性时,就被认为是完整的:
- 所有的 N-1 组件用于连接零件。
- 考虑一个图表 N 对应于零件的顶点和 N-1 无向边对应于由连接组件连接的顶点对。然后,这个图就连接起来了。
当满足以下条件时,使图形完整的两种方法 A 和 B 被认为是相同的:对于每对孔,A 使用连接组件来连接这些孔,当且仅当 B 使用一个连接组件来连接它们时。
找出使图形完整的方法数。由于答案可能很大,请求模数 998244353.
约束
- 输入中的所有值都是整数。
- 2 \leq N \leq 2 \times 10^5
- 1 \leq d_i < 998244353
输入
输入由标准输入按以下格式给出:
N d_1 d_2 \cdots d_N
输出
打印答案。
示例输入 1
3 1 1 3
示例输出 1
6
使图形完整的一种方法是连接孔 1 部分 1 和孔 3 部分 3 然后连接孔 1 部分 2 和孔 1 部分 3.
示例输入 2
3 1 1 1
示例输出 2
0
示例输入 3
6 7 3 5 10 6 4
示例输出 3
389183858
示例输入 4
9 425656 453453 4320 1231 9582 54336 31435436 14342 423543
示例输出 4
667877982