「Wdsr-2」环
题目描述
Kagamine Rin 有一个圆环，上面均匀分布着 $n$ 个点，这些点之间连接着 $m$ 条线段。
突然有一天，这些线段全都不见了。
Rin 想要找回这些线段，但是她不记得线段的分布。她只记得，这些线段中任意两条都不相交。
**注意：只在端点处相交不算相交；重合不算相交。** 下面的样例解释有助于理解本题中的定义。
Rin 有时还会记得一些额外的信息，她可能还会告诉你每个点上连接的线段数。
现在 Rin 想要知道，符合她的记忆的方案数有多少种。由于结果可能很大，你只需要输出答案对 $1000000007$ 取模的结果（模数是一个质数）。
输入输出格式
输入格式
第一行输入三个整数 $n,m,type$。
如果 $type=1$，接下来一行输入 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个点上连接的线段数。数据保证 $\sum_{i=1}^na_i=2m$。
输出格式
输出只有一个整数，表示合法的方案数对 $1000000007$ 取模的结果。
输入输出样例
输入样例 #1
4 2 0
输出样例 #1
20
输入样例 #2
4 2 1
1 1 1 1
输出样例 #2
2
说明
样例解释：
**Update：上图第二行第三个画错了，它的竖应该在右边**
如上图，有 $20$ 种方案满足样例 $1$ 的要求，而只有最后两种方案满足样例 $2$ 的要求。
------
**本题采用捆绑测试**，数据范围遵守如下约定：
subtask | $n\le$ | $m\le$ | $type$ | 分数
:-:|:-:|:-:|:-:|:-:
$0$ | $8$ | $8$ | $0$ | $10$
$1$ | $50$ | $50$ | $0$ | $10$
$2$ | $4000$ | $4000$ | $0$ | $15$
$3$ | $8$ | $8$ | $1$ | $10$
$4$ | $50$ | $50$ | $1$ | $15$
$5$ | $600$ | $600$ | $1$ | $20$
$6$ | $4000$ | $4000$ | $1$ | $20$
对于所有数据，有 $2\le n\le 4000,1\le m\le 4000,type\in \{0,1\}, a_i \ge 0$。若 $type=1$ 则保证 $\sum_{i=1}^na_i=2m$。