Rabbit Game Playing#3403
In the game, a rabbit is passing levels, each with its own difficulty. The rabbit is ambitious and usually wants to play a stage which is more difficult than the previous one. However, sometimes, for rest, he allows himself to play a stage that is easier. But he agrees to play a stage only if its difficulty is not more than units easier than the previous one (that is, the previous stage's difficulty minus the next stage's difficulty is at most and not negative).
Your task is to determine in how many ways the rabbit can complete all the levels, while following this rule. Since the answer could be very large, print it modulo .
The first line contains two integers and (1 \leq N \leq 100\,000, 1 \leq T \leq 100\,000). Here, is the number of stages, and is the allowed maximum amount by which the next stage can be easier than the previous one.
The next lines contain an integer D_i (1 \leq D_i \leq 100\,000) — the difficulty of the -th stage.
Output the number of ways to complete all levels, modulo .
Example 1