#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

Qi the Chuan Shen (船神) has decided to build a tower using boats! Each boat *i* has a width *W _{i}*. In order to prevent the tower from toppling, Qi has calculated that a boat of width

*A*can only be placed directly on top of a boat of width

*B*if

*A*≤

*B*+

*Q*, where

*Q*is Qi's constant. Help Qi compute the number of different towers he can build using each of the

*N*boats exactly once!

Note: Two towers are different if the order of boats from bottom to top is different.

## Input

On the first line are space-separated integers*N*(1 ≤

*N*≤ 100,000) and

*Q*(1 ≤

*Q*≤ 1,000,000,000). The next

*N*lines contain an integer each, the

*i*

^{th}of which is the value

*W*(1 ≤

_{i}*W*≤ 1,000,000,000).

_{i}## Output

On the first and only line output the number of possible towers, modulo 1,000,000,007.## Sample Input 1

4 1 1 2 3 3

## Sample Output 1

12

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 20 | 1s | 32MB | Average |

2 | 0 | 1 | 1s | 32MB | Average |

### Judge Compile Command

g++-7 ans.cpp -o tower -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512