题目描述

Takahashi 正在组装一个字符雕塑，它由 $N$ 个部分和 $N-1$ 条连接组件组成。部分是可以区分的，但连接组件是无法区分的。

第 $i$ 个部分有 $d_i$ 个孔，分别称为孔 $1$，孔 $2$，...，孔 $d_i$，可以插入一个连接组件。部分上的这些孔是可以区分的。每个连接组件将被插入两个不同部分的孔中，连接这两个部分。无法在一个孔中插入多个连接组件。

当雕塑具有以下特征时，称之为完整的：

• 使用所有 $N-1$ 个连接组件连接各部分。
• 考虑一个图，其中有 $N$ 个顶点对应于各部分，有 $N-1$ 条无向边对应于连接组件连接的顶点对。那么，该图是连通的。

如果对于每一对孔，通过连接组件连接这些孔时，两种方式 A 和 B 被认为是相同的，当且仅当满足以下条件：A 使用一个连接组件连接这些孔，当且仅当 B 使用一个连接组件连接这些孔。

找出使雕塑完整的方法数。由于答案可能非常大，将计数模 $998244353$。

约束条件

• 输入中的所有值都是整数。
• $2 \le N \le 2 \times 10^5$
• $1 \le d_i < 998244353$

输入

从标准输入读取输入数据，格式如下：

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

输出

打印答案。

示例输入 1

3
1 1 3

示例输出 1

6

使雕塑完整的一种方法是连接 Part $1$ 的 Hole $1$ 和 Part $3$ 的 Hole $3$ ，然后连接 Part $2$ 的 Hole $1$ 和 Part $3$ 的 Hole $1$。

示例输入 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