题目描述

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$ 取模的结果。

4 2 0

20

4 2 1
1 1 1 1

2

提示

样例解释：

Update：上图第二行第三个画错了，它的竖应该在右边

如上图，有 $20$ 种方案满足样例 $1$ 的要求，而只有最后两种方案满足样例 $2$ 的要求。

本题采用捆绑测试，数据范围遵守如下约定：

对于所有数据，有 $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$。