Rabbit Game Playing

Time limit8sMemory limit512 MB

Summary

Count permutations of the N stage difficulties in which each next stage is either harder than all previous ones or at most T easier than the immediately preceding stage, modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Sorting, Binary search
Solved: No attempts yet

Problem

Honestly, the rabbit does not matter.

A rabbit is playing a stage-based action game. In this game, every stage has a difficulty level. The rabbit, who always needs a challenge, basically wants to play stages that are more difficult than any he has played before. But sometimes he needs rest too. So, as a compromise, he agreed to allow playing stages that are easier than the preceding one by at most T levels.

How many ways are there to play all the stages in one go while following the rule above? The answer may be large, so tell me the answer modulo 1, 000, 000, 007.

Input

The first line of input contains two integers N and T (1 ≤ N ≤ 100, 000, 1 ≤ T ≤ 100, 000). N is the number of stages, and T is the compromise level.

The following N lines describe the difficulty level of each stage. The i-th line contains one integer Di (1 ≤ Di ≤ 100, 000), the difficulty level of the i-th stage.

Output

Compute the number of ways to play all the stages in one go. Print the answer modulo 1, 000, 000, 007 on one line.

Examples3

Example 1
Input
```
3 1
1
2
3
```
Expected output
```
4
```
Example 2
Input
```
5 3
9
2
6
8
8
```
Expected output
```
24
```
Example 3
Input
```
5 7
9
9
9
1
5
```
Expected output
```
48
```