Given is an irregular staircase that consists of n steps, numbered 0 through n-1.
The height of step i is H[i].

Ada starts at the bottom of the staircase and wants to go to the top.
In each step she must climb at least one step of the staircase, but possibly more.
The only thing that limits her is that she is unable to cover a height difference of more than m in a single step.

Count the number of ways in which she can ascend the staircase, and report the count modulo 10^9 + 7.

-------------------------------------------------------------------------------------------------

The first line of input contains the integers n and m.
The second line contains the integers H[0] through H[n-1].

You may assume that:
1 <= n <= 500,000
1 <= H[i] <= 10^9
max(H[i]) <= m <= 10^9

-------------------------------------------------------------------------------------------------

Output a single line with the number of valid ways to ascend the staircase, modulo 1,000,000,007.

-------------------------------------------------------------------------------------------------

Example input:

4 100
20 30 50 30

Example output:

6

Explanation:

Below, we use the number i to denote the state where Ada already ascended i steps. So, for example,
01234 is the sequence where Ada starts at the bottom and goes to the top by stepping on each of the
intermediate steps.

These are the sequences that are valid ascensions for the above input: 01234, 0124, 0134, 0234, 024, 034.