题目描述

高桥君打算组装一个模型。这个模型由 $N$ 个部件（部件 $1$、部件 $2$、…、部件 $N$）和 $N-1$ 个连接件组成。各个部件彼此有区别，但所有连接件彼此没有区别。

部件 $i$ 上有 $d_i$ 个用于插入连接件的孔（孔 $1$、孔 $2$、…、孔 $d_i$）。每个部件上的孔彼此有区别。每个连接件可以插入两个部件的孔，将这两个部件连接起来。一个孔不能插入多个连接件。

满足以下性质的模型称为“完成形”：

• $N-1$ 个连接件全部用于连接部件。
• 以部件为顶点，若两个部件通过连接件连接，则在这两个顶点之间连一条边，得到一个 $N$ 个顶点、$N-1$ 条边的无向图。此图是连通的。

对于两个完成形，如果对于所有孔的组合，是否存在连接件连接这两个孔的情况完全一致，则认为这两个完成形是相同的。

请问有多少种不同的完成形？由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入格式

输入以以下格式从标准输入给出。

$N$ $d_1$ $d_2$ $\cdots$ $d_N$

输出格式

请输出答案。

样例 1

输入

3
1 1 3

输出

6

样例 2

输入

3
1 1 1

输出

0

样例 3

输入

6
7 3 5 10 6 4

输出

389183858

样例 4

输入

9
425656 453453 4320 1231 9582 54336 31435436 14342 423543

输出

667877982

说明/提示

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq d_i < 998244353$

样例解释 1

例如，将部件 $1$ 的孔 $1$ 与部件 $3$ 的孔 $3$ 连接，将部件 $2$ 的孔 $1$ 与部件 $3$ 的孔 $1$ 连接，这样组装的模型也被视为一种完成形。

由 ChatGPT 4.1 翻译