Problem Description

There are \(N\\) tubes with different colors, each containing \(a\_1\\), \(a\_2\\), ..., \(a\_N\\) balls of the same color as the tube. The total number of balls in all tubes combined is \(M\\).

The width of each tube is exactly enough for one ball. There are no empty tubes.

Ayako came up with the following game: rearrange the balls from the tubes under the following conditions:

• The number of balls in each tube remains unchanged from the initial state.
• The color of the balls in each tube is different from the color of the tube.

How many ways are there to rearrange the balls under these conditions? Find the answer modulo \(10^9+7\\).

Note that the distinction between balls of the same color is not made, but the order of the colors in the tubes is distinguished.

Input Format

The input is given from the standard input in the following format:

```
\(N\) \(M\)
\(a_1\) \(a_2\) \(\dots\) \(a_N\)

## Output Format

Output the answer to the problem in one line.

## Sample Input and Output

### Sample Input #1

2 4
2 2

### Sample Output #1

1

### Sample Input #2

3 5
2 2 1

### Sample Output #2

4

### Sample Input #3

4 15
2 2 1 10

### Sample Output #3

0
```

Notes/Hints

Constraints

• \(1 \\leq N \\leq 2000\\)
• \(1 \\leq M \\leq 2000\\)
• \(1 \\leq a\_i \\leq M\\)
• \(\\sum a\_i = M\\)
• All values given in the input are integers.

Sample Explanation 1

The only way to satisfy the conditions is to swap the two balls as shown in the figure below, so the answer is 1 way.

Sample Explanation 3

No matter how the balls are arranged, the conditions cannot be satisfied.

见题面 Input 部分

见题面 Output 部分