← 返回题目列表

AtCoder · asaporo2_f

F. 单循环图计数

中文机器翻译题面 查看原题

分数: 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
  • 共有六张图,如下所示:
51367cdb21c64bfb07113b300921d52c.png

示例输入 2

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

示例输出 2

555275958
  • 一定要找到模数的答案 10^{9} + 7.