← 返回题目列表

AtCoder · arc106_f

F. 数字

中文机器翻译题面 查看原题

分数: 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