Problem Description

The "sealing of the leaderboard" is a unique mechanism in the ICPC series competitions. ICPC competitions are real-time feedback programming contests where participants and spectators can view the number of problems solved and rankings of each team on the leaderboard. During the last hour of the competition, the leaderboard is "sealed," hiding the results of submissions made in that final hour. After the competition, the rolling leaderboard phase reveals the number of problems each team solved in the last hour.

Alice witnessed the rolling leaderboard phase of an ICPC competition. There were $n$ teams participating, numbered from $1$ to $n$, with team $i$ having solved $a_i$ problems before the leaderboard was sealed. The leaderboard ranks teams by the number of problems solved in descending order; if two teams have solved the same number of problems, the team with the smaller number ranks higher.

During the rolling leaderboard, the organizers announced the number of problems each team solved after the seal ($b_i$) in non-decreasing order ($b_i$). Each announcement updated the leaderboard in real-time. Alice does not remember the order of the announcements or the final rankings but knows that each announced team became the new leader on the leaderboard and that all teams together solved $m$ problems after the seal ($\sum_{i=1}^{n} b_i = m$).

Alice wants you to calculate how many possible final rankings of the teams there could be.

Input Format

The first line contains two positive integers $n$ and $m$, representing the number of teams and the total number of problems solved after the seal, respectively.
The second line contains $n$ positive integers, representing $a_i$.

Output Format

A single line containing an integer, representing the answer.

Sample Input and Output

Sample Input #1

3 6
1 2 1

Sample Output #1

5

Sample Input #2

6 50
4 7 9 3 0 3

Sample Output #2

96

Sample Input #3

11 300
6 8 8 12 0 11 6 1 0 15 5

Sample Output #3

30140983

Notes/Hints

[Sample #1 Explanation]

1. Final ranking: $1, 3, 2$, rolling leaderboard: $b_2 = 0$, $b_3 = 2$, $b_1 = 4$.
2. Final ranking: $2, 1, 3$, rolling leaderboard: $b_3 = 2$, $b_1 = 2$, $b_2 = 2$.
3. Final ranking: $2, 3, 1$, rolling leaderboard: $b_1 = 1$, $b_3 = 2$, $b_2 = 3$.
4. Final ranking: $3, 1, 2$, rolling leaderboard: $b_2 = 0$, $b_1 = 2$, $b_3 = 4$.
5. Final ranking: $3, 2, 1$, rolling leaderboard: $b_1 = 1$, $b_2 = 1$, $b_3 = 4$.

[Data Range]

For all test cases: $1 \le n \le 13$, $1 \le m \le 500$, $0 \le a_i \le 10^4$.

Specific restrictions for each test point are as follows:

见题面 Input 部分

见题面 Output 部分