题目描述

高橋君はフィギュアを組み立てようとしています。このフィギュアは、 $N$ 個の部品(部品 $1$ , 部品 $2$ , ..., 部品 $N$ )と、 $N-1$ 個の接続用部品から成ります。部品同士は区別が出来ますが、接続用部品同士は区別が出来ません。

部品 $i$ には、$d_i$ 個の接続用部品を挿す穴(穴 $1$ , 穴 $2$ , ..., 穴 $d_i$ )が空いています。各部品の穴同士は区別が出来ます。 各接続用部品は、 $2$ 個の部品の穴に挿し込まれ、それら $2$ 個の部品を接続します。 $1$ つの穴に複数の接続用部品を挿し込むことは出来ません。

以下の性質を満たすフィギュアのことを、完成形と呼びます。

• $N-1$ 個の接続用部品が全て部品の接続に使われている。
• 部品を頂点とし、 接続用部品で接続された部品に対応する頂点組に辺が存在する $N$ 頂点 $N-1$ 辺の無向グラフを考えた際に、このグラフは連結である。

$2$ つの完成形について、全ての穴の組についてその $2$ つを接続する接続用部品が存在するか否かが一致するとき、$2$ つの完成形が同じであると見なします。

完成形が何種類あるかを答えてください。 ただし、答えは非常に大きくなることがあるので、 $998244353$ で割った余りを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $d_1$ $d_2$ $\cdots$ $d_N$

输出格式

答えを出力せよ。

题目大意

有 $N$ 个点，每个点有 $a_i$ 个孔，每次可以选择两个不同点，连接两个未被连接过的孔，有多少中方案使得最后形成一棵树。

3
1 1 3

6

3
1 1 1

0

6
7 3 5 10 6 4

389183858

9
425656 453453 4320 1231 9582 54336 31435436 14342 423543

667877982

提示

制約

• 入力は全て整数
• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ d_i\ <\ 998244353$

Sample Explanation 1

例えば、部品 $1$ の穴 $1$ と部品 $3$ の穴 $3$ を接続し、部品 $2$ の穴 $1$ と部品 $3$ の穴 $1$ を接続したフィギュアは、完成形として認められます。