Potato Shuffle
시간 제한1초메모리 제한512 MB
감자 자루가 일렬로 있을 때 무게 합이 k 이하인 인접한 두 자루만 교환할 수 있으며, 이렇게 도달 가능한 배열의 수를 10^9+7로 나눈 나머지를 구한다.
문제
Marichka has a lot of potato in her basement. There are n bags with potato in a line. The i-th of them contains ai potatoes.
Zenyk loves to shuffle those bags. During one shuffle operation he can grab two adjacent bags and swap their positions if the total number of potatoes in this two bags does not exceed number k. Zenyk can perform as many shuffle operations as he wishes.
Once Zenyk and Marichka wondered, what is the total number of bag permutations Zenyk can achieve. Two bag permutations are considered different if there is a position where two bags have different number of potatoes.
입력
The first line contains two integers n (1 ≤ n ≤ 105) and k (0 ≤ k ≤ 2 · 109). The second line contains n integers ai (1 ≤ ai ≤ 109).
출력
Single integer — the number of different permutations modulo 109 + 7.