201555: [AtCoder]ARC155 F - Directable as Desired

Memory Limit:1024 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

加入题单

上一题 下一题 算法标签: