F - Directable as Desired Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

長さ N の非負整数列 D=(D_1, D_2, \dots, D_N) が与えられます。

1 から N までの番号が付いた 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

条件を満たす木（およびその向き付けの例）は下の 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

Score : 1000 points

Problem Statement

You are given a sequence of N non-negative integers: D=(D_1, D_2, \dots, D_N).

Find the number of labeled trees with N vertices numbered 1 to N that satisfy the following condition, modulo 998244353.

  • There is a way to direct the N-1 edges so that the outdegree of each vertex i\ (1\leq i \leq N) is D_i.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq D_i \leq N-1
  • \sum_{i=1}^{N} D_i = N-1
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
D_1 D_2 \dots D_N

Output

Print the answer.

Sample Input 1

4
0 1 0 2

Sample Output 1

5

Below are the five trees that satisfy the condition, directed in a desired way.

Sample Input 2

5
0 1 1 1 1

Sample Output 2

125

Sample Input 3

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

Sample Output 3

63282877