Stable Snack Stacking

You are given a box which is divided into n piles (numbered from 1 to n from left to right) where snacks (each of size \(1 \times 1\)) can be placed. In each pile, the number of snacks is represented by \(h_i\) (which can be 0) and must satisfy \(h_i \le m\). A pile is said to be stable if:

• \(h_i \le m\); and
• One of the following holds:
  • It is at one of the boundaries, i.e. \(i = 1\) or \(i = n\) (because the box wall supports it), or
  • \(\max\{h_{i-1}, h_{i+1}\} \ge h_i - d_i\)

A stable stacking method is a sequence \(h_1, h_2, \ldots, h_n\) (with \(0 \le h_i \le m\)) such that every pile is stable under the above rules. You may assume that there are enough snacks (at least \(n \times m\)) so that not all snacks are required.

Find the number of stable stacking methods. Since the answer can be large, output it modulo \(10^9+7\).

Note: When submitting your solution, O2 optimization is automatically enabled.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of piles and the maximum allowed height per pile respectively).

The second line contains \(n\) integers: \(d_1, d_2, \ldots, d_n\), where \(d_i\) is used in the stability condition for pile \(i\) (note that for the boundary piles, this value is not used).

outputFormat

Output a single integer, the number of stable stacking methods modulo \(10^9+7\).

sample

1 2
0

3