AT_arc106_f [ARC106F] Figures

[problemUrl]: https://atcoder.jp/contests/arc106/tasks/arc106_f 高橋君はフィギュアを組み立てようとしています。このフィギュアは、 $ 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/A

N/A

### 制約 - 入力は全て整数 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ d_i\