"Freezing the scoreboard" is a characteristic mechanism in ICPC-style contests. ICPC contests are programming competitions with real-time feedback, where participants and spectators can view the number of problems solved and the current ranking of each team in real-time. During the last hour of the contest, the scoreboard is "frozen," meaning that the results of submissions made during the last hour are hidden. After the contest, the results of the last hour (i.e., the number of problems solved by each team during the last hour) are revealed during the "ranklist" ceremony.
Alice watched the ranklist ceremony of an ICPC contest. There were $n$ teams in this contest, numbered $1 \sim n$. The number of problems solved by team $i$ before the freeze was $a_i$. Teams are ranked on the scoreboard in descending order of the number of problems solved; if two teams have the same number of problems solved, the team with the smaller ID is ranked higher.
During the ranklist ceremony, the organizers announced the number of problems solved by each team after the freeze, denoted as $b_i$ (the final total number of problems solved by the team is $a_i + b_i$), in non-decreasing order of $b_i$. Furthermore, every time a team's result was announced, the rankings on the scoreboard were updated in real-time. Alice does not remember the order in which the teams were announced, nor does she remember the final rankings on the scoreboard. She only remembers that after each announcement, the team whose result was just announced became the first place on the new scoreboard, and that the total number of problems solved by all teams after the freeze was $m$ (i.e., $\sum_{i=1}^n b_i = m$).
Now, Alice wants you to help her calculate how many possible final rankings there are on the scoreboard.
Input
The first line contains two positive integers $n$ and $m$, representing the number of teams and the total number of problems solved by them after the freeze.
The second line contains $n$ positive integers representing $a_i$.
Output
Output a single integer representing the answer.
Examples
Input 1
3 6 2 1 2 1
Output 1
5
Note 1
- Final ranking: 1, 3, 2, ranklist details (in order of announcement, same below): $b_2 = 0, b_3 = 2, b_1 = 4$.
- Final ranking: 2, 1, 3, ranklist details: $b_3 = 2, b_1 = 2, b_2 = 2$.
- Final ranking: 2, 3, 1, ranklist details: $b_1 = 1, b_3 = 2, b_2 = 3$.
- Final ranking: 3, 1, 2, ranklist details: $b_2 = 0, b_1 = 2, b_3 = 4$.
- Final ranking: 3, 2, 1, ranklist details: $b_1 = 1, b_2 = 1, b_3 = 4$.
Input 2
6 50 4 7 9 3 0 3
Output 2
96
Input 3
11 300 6 8 8 12 0 11 6 1 0 15 5
Output 3
30140983
Constraints
For all test data: $1 \le n \le 13$, $1 \le m \le 500$, $0 \le a_i \le 10^4$.
The specific limits for each test case are shown in the table below:
| Test Case 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$ |