P7519 [NOI Qualifier Joint Contest 2021 A/B] Scoreboard Roll

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.

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$.

Only one line with one integer, the answer.

**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: | Test point ID | $n \le$ | $m \le$ | |:-:|:-:|:-:| | $1 \sim 2$ | $2$ | $10$ | | $3 \sim 5$ | $3$ | $10$ | | $6 \sim 8$ | $8$ | $100$ | | $9 \sim 12$ | $10$ | $200$ | | $13 \sim 16$ | $12$ | $300$ | | $17 \sim 20$ | $13$ | $500$ | Translated by ChatGPT 5