配点 : $800$ 点

問題文

高橋君はフィギュアを組み立てようとしています。このフィギュアは、 $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$ で割った余りを出力してください。

制約

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

入力

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

$N$

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

出力

答えを出力せよ。

3
1 1 3

6

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

3
1 1 1

0

6
7 3 5 10 6 4

389183858

9
425656 453453 4320 1231 9582 54336 31435436 14342 423543

667877982