问题陈述

给定一个由 $N$ 个非负整数组成的序列 $D=(D_1, D_2, \dots, D_N)$。

找到满足以下条件的标记树的数量，对 $998244353$ 取模。

• 存在一种方式将 $N-1$ 条边指定方向，使得每个顶点 $i\ (1\leq i \leq N)$ 的出度为 $D_i$。

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq D_i \leq N-1$
• $\sum_{i=1}^{N} D_i = N-1$
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入读取：

$N$ $D_1$ $D_2$ $\dots$ $D_N$

输出

输出答案。

示例输入 1

4
0 1 0 2

示例输出 1

5

满足条件的五棵树如下所示，以期望的方式进行了指定方向。

示例输入 2

5
0 1 1 1 1

示例输出 2

125

示例输入 3

15
0 0 0 0 0 0 0 1 1 1 1 1 2 3 4

示例输出 3

63282877