eolymp
bolt
Try our new interface for solving problems
Problems

Rabbit Game Playing

Rabbit Game Playing

Time limit 1 second
Memory limit 64 MiB

Honestly, a rabbit does not matter.

There is a rabbit playing a stage system action game. In this game, every stage has a diffculty level. The rabbit, which always needs challenges, basically wants to play more diffcult stages than he has ever played. However, he sometimes needs rest too. So, to compromise, he admitted to play T or less levels easier stages than the preceding one.

How many ways are there to play all the stages at once, while honoring the convention above? Maybe the answer will be a large number. So, let me know the answer modulo 1000000007.

Input data

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

The following N lines describe the diffculty levels of each stage. The i^th line contains one integer D_i (1D_i100000), which is the diffculty level of the i^th stage.

Output data

Calculate how many ways to play all the stages at once there are. Print the answer modulo 1000000007 in a line.

Examples

Input example #1
3 1
1
2
3
Output example #1
4
Source The 2011 35th Annual ACM Programming Contest Winter Camp