分数: 1000 点
问题陈述
Snuke 遇到了以下问题。
给你一个序列 d 长度 N。 查找无向图的数量 N 顶点标记 1,2,...,N 满足以下条件,取模 10^{9} + 7:
- 该图简单且连通。
- 顶点度数 i is 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)!}.
Snuke 想知道答案是什么 当 3 \leq N, 1 \leq d_i \leq N-1, { \rm Σ} d_i = 2N. 帮他解决这个条件下的问题。
约束
- 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.
输入
输入由标准输入按以下格式给出:
N
d_1 d_2 ... d_{N}
输出
打印答案。
示例输入 1
5 1 2 2 3 2
示例输出 1
6
- 共有六张图,如下所示:
示例输入 2
16 2 1 3 1 2 1 4 1 1 2 1 1 3 2 4 3
示例输出 2
555275958
- 一定要找到模数的答案 10^{9} + 7.