Unicyclic Graph Counting

### 题目大意 求有多少$N$个点的环套树，满足第$i$个点的度数为给定的$d_i$。答案对$10^9+7$取模。 环套树是一个$n$个点、$n$条边的简单（无重边、无自环）联通无向图。 ### 输入格式 第一行一个正整数$N$，表示点的个数。 第二行有$N$个整数$d_i$，表示每个点的度数。 ### 输出格式 输出仅一行一个整数为答案，答案对$10^9+7$取模。 ### 数据范围 - $3 \le N \le 300$ - $1 \le d_i \le N - 1$ - $\Sigma{d_i} = 2N$ 翻译提供者：浮尘ii

[problemUrl]: https://atcoder.jp/contests/cf17-tournament-round3-open/tasks/asaporo2_f すぬけくんは以下のような問題を考えました。 > 長さ $ N $ の数列 $ d $ が与えられます。 以下の条件を満たす頂点に $ 1,2,...,N $ のラベルがついた $ N $ 頂点の無向グラフの数を modulo $ 10^{9}\ +\ 7 $ で求めてください。 > > - グラフは単純かつ連結 > - 頂点 $ i $ の次数は $ d_i $ **$ 　2\ \leq\ N,\ 1\ \leq\ d_i\ \leq\ N-1,\ {\rm\ Σ}\ d_i\ =\ 2(N-1) $ を満たす場合** には、この問題の答えは $ \frac{(N-2)!}{(d_{1}\ -1)!(d_{2}\ -\ 1)!\ ...\ (d_{N}-1)!} $ で表せることが証明できます。 すぬけくんは **$ 3\ \leq\ N,\ 1\ \leq\ d_i\ \leq\ N-1,\ {\ \rm\ Σ}\ d_i\ =\ 2N $ を満たす場合** どうなるかが気になっています。 すぬけくんの代わりにこの問題を解いてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ d_1 $ $ d_2 $ $ ... $ $ d_{N} $

答えを出力せよ。

5
1 2 2 3 2

6

16
2 1 3 1 2 1 4 1 1 2 1 1 3 2 4 3

555275958

### 制約 - $ 3\ \leq\ N\ \leq\ 300 $ - $ 1\ \leq\ d_i\ \leq\ N-1 $ - $ {\ \rm\ Σ}\ d_i\ =\ 2N $ ### 部分点 - $ 200 $ 点分のデータセットでは $ N\ \leq\ 5 $ が成立する - 別の $ 200 $ 点分のデータセットでは $ N\ \leq\ 18 $ が成立する - 別の $ 300 $ 点分のデータセットでは $ N\ \leq\ 50 $ が成立する ### Sample Explanation 1 \- 以下の図に示されるような $ 6 $ 通りです !\[51367cdb21c64bfb07113b300921d52c.png\](https://atcoder.jp/img/asaporo2/51367cdb21c64bfb07113b300921d52c.png) ### Sample Explanation 2 \- $ 10^{9}\ +\ 7 $ で割ったあまりを求めてください