Problem Description

Kagamine Rin has a circular ring with $n$ points evenly placed on it, and there are $m$ line segments connecting these points.

Suddenly one day, all these line segments disappeared.

Rin wants to recover these line segments, but she does not remember their arrangement. She only remembers that no two of these line segments intersect.

Note: touching only at endpoints is not considered an intersection; overlapping is not considered an intersection. The sample explanation below helps to understand the definition used in this problem.

Sometimes Rin also remembers some extra information: she may tell you the number of line segments incident to each point.

Now Rin wants to know how many different arrangements satisfy her memory. Since the result may be large, you only need to output the answer modulo $1000000007$ (the modulus is a prime number).

Input Format

The first line contains three integers $n, m, type$.

If $type = 1$, the next line contains $n$ integers. The $i$-th integer $a_i$ represents the number of line segments incident to the $i$-th point. The testdata guarantees that $\sum_{i=1}^n a_i = 2m$.

Output Format

Output a single integer, the number of valid arrangements modulo $1000000007$.

4 2 0

20

4 2 1
1 1 1 1

2

Hint

Sample explanation:

Update: in the second row, the third drawing in the figure above is wrong; its vertical line should be on the right.

As shown above, there are $20$ arrangements that satisfy the requirements of Sample 1, and only the last two arrangements satisfy the requirements of Sample 2.

This problem uses bundled tests, and the Constraints follow the table below:

For all testdata: $2 \le n \le 4000$, $1 \le m \le 4000$, $type \in \{0,1\}$, $a_i \ge 0$. If $type = 1$, then it is guaranteed that $\sum_{i=1}^n a_i = 2m$.

Translated by ChatGPT 5