Non-Attracting Magnets

Given n magnets and l slots arranged in a line with adjacent slots at a distance of 1, each slot can hold at most one magnet. Each magnet i has an attraction range ri and will attract any other magnet if the distance between them is less than ri. All n magnets must be placed. Determine the number of ways to place the magnets so that no magnet attracts any other. Since the answer can be very large, output it modulo \(10^9+7\).

Note: When the magnets are placed in increasing order on the slots, let their positions be \(p_1, p_2, \dots, p_n\) (with \(p_1<p_2<\cdots<p_n\)). Then for each magnet the only possible magnets that could be attracted are its immediate neighbors. In order for magnet 1 (which has only a right neighbor) not to attract any other magnet, it is required that \[ p_2-p_1\ge r_1. \] For magnet \(i\) (with \(2\le i\le n-1\)) the condition is \[ p_i-p_{i-1}\ge r_i \quad\text{and}\quad p_{i+1}-p_i\ge r_i, \] while magnet \(n\) must satisfy \[ p_n-p_{n-1}\ge r_n. \]

This set of constraints is equivalent to requiring that for every gap between consecutive magnets (i.e. for \(2\le i\le n\)) the gap \(g_i=p_i-p_{i-1}\) satisfies \[ g_i\ge d_i, \quad\text{where}\quad d_i=\max(r_{i-1},r_i). \]

If \(n\ge2\), define \(P=l-1-\sum_{i=2}^{n}d_i\). Then, by letting \(x=p_1-1\) and \(y_i=g_i-d_i\) (for \(2\le i\le n\)), the problem reduces to counting the number of nonnegative integer solutions to \[ x+\sum_{i=2}^{n} y_i\le P,\] which is given by the stars and bars formula \[ \binom{P+n}{n}. \] In the special case \(n=1\), there is no gap constraint and the answer is simply \(l\).

Output the result modulo \(10^9+7\).

inputFormat

The first line contains two integers n and l (\(1\le n\le l\le \text{some upper bound}\)).

The second line contains n integers: r1, r2, …, rn.

outputFormat

Output a single integer representing the number of valid placement schemes modulo \(10^9+7\).

sample

1 5
3

5