题目描述

すぬけくんは以下のような問題を考えました。

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

输出格式

答えを出力せよ。

题目大意

题目大意

求有多少$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

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$ 通りです 

Sample Explanation 2

- $10^{9}\ +\ 7$ で割ったあまりを求めてください