题目描述

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

请计算有多少个满足以下条件的、编号为 $1$ 到 $N$ 的 $N$ 个顶点的有标号树，并将答案对 $998244353$ 取模：

• 可以对 $N-1$ 条边进行适当的定向，使得每个顶点 $i\ (1\leq i \leq N)$ 的出度恰好为 $D_i$。

输入格式

输入通过标准输入按以下格式给出。

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

输出格式

请输出答案。

样例 1

输入

4
0 1 0 2

输出

5

样例 2

输入

5
0 1 1 1 1

输出

125

样例 3

输入

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

输出

63282877

说明/提示

限制条件

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

样例解释 1

满足条件的树（以及其一种定向方式）如下图所示，共有 $5$ 种。

由 ChatGPT 4.1 翻译