問題文

長さ $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