Description

Scoreboard freezing is a special mechanism in the ICPC series contests. An ICPC contest is a programming contest where submission results are shown in real time, and contestants and the audience can view each team’s solved problem count and ranking on the scoreboard in real time. During the last hour of the contest, the scoreboard will be “frozen”, meaning that the results of submissions made in the last hour are hidden on the scoreboard. After the contest, in the scoreboard roll session, the results of the last hour (that is, the number of problems each team solved in the last hour) are revealed.

Alice watched the scoreboard roll session of an ICPC contest. There are $n$ teams in this contest, numbered from $1$ to $n$. Before the scoreboard was frozen, team $i$ had solved $a_i$ problems. On the scoreboard, teams are ranked by solved problem count in decreasing order. If two teams have the same solved count, the team with the smaller index ranks higher.

During the roll, the organizers revealed each team’s post-freeze solved count $b_i$ in non-decreasing order of $b_i$ (so the final total solved count of that team is $a_i + b_i$). Each time a team’s result is revealed, the scoreboard updates the rankings in real time. Alice does not remember the order in which teams were revealed, nor the final ranking on the scoreboard. She only remembers that after each reveal, the team whose result was revealed became the new first place on the updated scoreboard, and that in total all teams solved $m$ problems after the freeze (i.e., $\sum_{i = 1}^{n} b_i = m$).

Now Alice wants you to help her compute how many different final rankings are possible.

Input Format

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

Output Format

Only one line with one integer, the answer.

3 6
1 2 1

5

6 50
4 7 9 3 0 3

96

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

30140983

Hint

Sample #1 Explanation

1. Final ranking: $1, 3, 2$. Roll process (in reveal order, same below): $b_2 = 0$, $b_3 = 2$, $b_1 = 4$.

2. Final ranking: $2, 1, 3$. Roll process: $b_3 = 2$, $b_1 = 2$, $b_2 = 2$.

3. Final ranking: $2, 3, 1$. Roll process: $b_1 = 1$, $b_3 = 2$, $b_2 = 3$.

4. Final ranking: $3, 1, 2$. Roll process: $b_2 = 0$, $b_1 = 2$, $b_3 = 4$.

5. Final ranking: $3, 2, 1$. Roll process: $b_1 = 1$, $b_2 = 1$, $b_3 = 4$.

Constraints

For all testdata: $1 \le n \le 13$, $1 \le m \le 500$, $0 \le a_i \le {10}^4$.

The specific limits for each test point are shown in the table below:

Translated by ChatGPT 5