토끼 게임 플레이

시간 제한8초메모리 제한512 MB

요약

N개 스테이지의 난이도를 모두 한 번씩 플레이하는 순열 중에서, 다음 스테이지가 이전 최고 난이도보다 어렵거나 직전 난이도보다 많아야 T만큼 쉬운 경우의 수를 1e9+7로 나눈 나머지를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 조합론, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

솔직히 토끼는 중요하지 않다.

한 토끼가 스테이지 방식 액션 게임을 하고 있다. 이 게임에서 모든 스테이지는 난이도를 가진다. 늘 도전이 필요한 토끼는 기본적으로 지금까지 해 본 것보다 어려운 스테이지를 하고 싶어 한다. 하지만 가끔은 휴식도 필요하다. 그래서 타협안으로, 바로 앞 스테이지보다 T 이하만큼 쉬운 스테이지를 하는 것도 허용하기로 했다.

위 규칙을 지키면서 모든 스테이지를 한 번에 플레이하는 방법은 몇 가지인가? 답이 클 수도 있으니 1, 000, 000, 007로 나눈 나머지를 알려 달라.

입력

첫 줄에 두 정수 N과 T가 주어진다 (1 ≤ N ≤ 100, 000, 1 ≤ T ≤ 100, 000). N은 스테이지의 수, T는 타협 수준이다.

다음 N개의 줄에 각 스테이지의 난이도가 주어진다. i번째 줄에는 정수 Di가 하나 주어진다 (1 ≤ Di ≤ 100, 000). 이는 i번째 스테이지의 난이도이다.

출력

모든 스테이지를 한 번에 플레이하는 방법의 수를 계산한다. 답을 1, 000, 000, 007로 나눈 나머지를 한 줄에 출력한다.

예제3

예제 1
입력
```
3 1
1
2
3
```
예상 출력
```
4
```
예제 2
입력
```
5 3
9
2
6
8
8
```
예상 출력
```
24
```
예제 3
입력
```
5 7
9
9
9
1
5
```
예상 출력
```
48
```