Counting Final Rankings in ICPC Rollboard

In the ICPC series there is a special mechanism called scoreboard freeze. Before the freeze, team i (for i = 1, 2, \(\dots, n\)) has solved \(a_i\) problems. After the freeze, each team "solves" additional problems during the last hour, but the results are hidden. In the roll‐board phase the frozen results \(b_i\) (with \(\sum_{i=1}^{n} b_i = m\)) are revealed one by one in non‐decreasing order (i.e. \(b_{i_1} \le b_{i_2} \le \dots \le b_{i_n}\) for the order of revelation). Each time a team’s result is announced, the scoreboard is updated immediately and the announced team becomes the new leader (rank 1). The final scoreboard is determined by the total problems solved \(t_i = a_i + b_i\) (with ties broken by the smaller team number).

More formally, suppose the final ranking (from 1^st to last) is given by a permutation \(P = [P_0,P_1,\dots,P_{n-1}]\) of \(\{1,2,\dots,n\}\) (where \(P_0\) is the champion). Then the revelation order is the reverse of \(P\), i.e. \(R = [P_{n-1},P_{n-2},\dots,P_0]\). When a team \(R[i]\) (with \(0\le i\le n-1\)) is revealed, let the set of unrevealed teams be those in \(\{P_0,P_1,\dots,P_{n-2-i}\}\). Define \[ M_i = \begin{cases} \max\{a_j: j \in \{P_0,\dots,P_{n-2-i}\}\}, & \text{if nonempty},\\ -\infty, & \text{if empty}. \end{cases} \] Also, let the already revealed teams have final scores with highest value \(prev\) (initially \(prev=-\infty\)). Then in order for team \(R[i]\) to become leader when revealed, we must have \[ a_{R[i]} + b_{R[i]} > \max(prev, M_i). \] For each \(R[i]\) a minimum extra score is required: \[ x_i = \max(0, \max(prev, M_i) - a_{R[i]} + 1). \] After revealing \(R[i]\) the new leader’s final score is updated to \(prev = a_{R[i]} + b_{R[i]}\). Moreover, because the results are announced in non‐decreasing order, the extra scores \(b_{R[0]}, b_{R[1]}, \dots, b_{R[n-1]}\) must form a non–decreasing sequence. In other words, if we define a transformed sequence \(y\) by forcing the minimum values \(x_i\) into a non–decreasing sequence (i.e. \(y_0 = x_0\) and \(y_i = \max(y_{i-1}, x_i)\) for \(i\ge1\)), then a necessary and sufficient condition for the existence of an assignment \(\{b_i\}\) with \(\sum_{i=1}^{n} b_i = m\) is that \[ \sum_{i=0}^{n-1} y_i \le m. \]

Your task is: given the number of teams (n), the total extra problems solved (m) and the pre-freeze scores (a_1, a_2, \dots, a_n), count how many different final ranking orders (i.e. permutations of the teams) can be achieved by some valid assignment of extra scores ({b_i}; (b_i \ge 0, , \sum b_i = m)) that also permits a revelation order (with the extra scores in non–decreasing order) in which the announced team always becomes the new leader.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 8\); the constraints are small so that all \(n!\) permutations can be checked), representing the number of teams and the total extra problems solved respectively. The second line contains \(n\) non–negative integers \(a_1, a_2, \dots, a_n\) where \(a_i\) is the number of problems solved by team \(i\) before the freeze. It is guaranteed that \(0 \le a_i \le 10^9\) and \(\sum_{i=1}^{n} b_i = m\) where \(b_i\) will be assigned by you subject to the conditions described.

outputFormat

Output a single integer: the number of possible final ranking orders that can be achieved.

sample

2 3
1 0

1