Problem: Honestly, a rabbit does not matter.

There is a rabbit playing a stage system action game. In this game, every stage has a difficulty level. The rabbit, which always needs challenges, basically wants to play more difficult 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 1,000,000,007.



Input

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

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

Output

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

Examples

Input

3 1
1
2
3


Output

4


Input

5 3
9
2
6
8
8


Output

24


Input

5 7
9
9
9
1
5


Output

48

Solution (in CPP):

Solution:
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;


template <int M, bool IsPrime = false>
class modulo {
    using ll = long long;
public:
    modulo() : n(0) {}
    modulo(int m) : n(m) {
        if(n >= M) {
            n %= M;
        } else if(n < 0) {
            n = (n % M + M) % M;
        }
    }
    modulo(ll m) {
        if(m >= M) {
            m %= M;
        } else if(m < 0) {
            m = (m % M + M) % M;
        }
        n = m;
    }

    explicit operator int() const {
        return n;
    }
    explicit operator ll() const {
        return n;
    }
    bool operator==(modulo const& a) const {
        return n == a.n;
    }

    modulo& operator+=(modulo const& a) {
        n += a.n;
        if(n >= M) {
            n -= M;
        }
        return *this;
    }
    modulo& operator-=(modulo const& a) {
        n -= a.n;
        if(n < 0) {
            n += M;
        }
        return *this;
    }
    modulo& operator*=(modulo const& a) {
        n = (ll(n) * a.n) % M;
        return *this;
    }
    modulo operator^(int n) const {
        if(n == 0) {
            return modulo(1);
        }
        const modulo a = *this;
        modulo res = (a * a) ^ (n / 2);
        return n % 2 ? res * a : res;
    }
   
    // for C++11, enable_if_t -> typename enable_if::type
    typename std::enable_if<IsPrime, modulo>::type operator/(modulo const& a) const {
        return *this * modulo(inv(ll(a), M));
    }


private:
    int n;
    // ax %% 1 (mod p)
    // ex: 5x %% 1 (mod 13)
    // テ」ツ?、テ」ツ?セテ」ツつ?5x + 13y = 1
    // テ、ツクツ。ティツセツコmod5テ」ツつ津・ツ渉姪」ツつ古」ツ?ーテッツシツ?3y %% 1 (mod 5) テ」ツ?、テ」ツ?セテ」ツつ?3y %% 1 (mod 5)テ」ツ?ォテ」ツ?ェテ」ツつ凝ッツシツ?
    // x = (1 - 13y) / 5 + 13 (+13テ」ツ?ッテヲツュツ」テ」ツ?ォテ」ツ?療」ツ?淌」ツ??」ツ?凝」ツつ?テ」ツ?ェテ」ツ?ョテ」ツ?ァテッツシツ古」ツ?禿」ツ??」ツ??」ツ??テ」ツ?古」ツ?サテ」ツ?療」ツ??」ツ?古ッツシツ?
    // テ・ツ?暗」ツ?サテ」ツ?ゥテ」ツ?ョ 3y %% 1 (mod 5) ティツァツ」テ」ツ?妥」ツ?ーティツ可ッテ」ツ??ッツシツ偲」ツ?禿」ツつ古」ツ?ッテ」ツ?、テ」ツ?セテ」ツつ甘ッツシツ景nv(13%5, 5) テ」ツ?ァテ」ツ?づ」ツつ凝ッツシツ?
    // テ」ツつ?」ツ?暗」ツ?ォテッツシツ警 = (1 - 13*inv(13%5, 5))/5 + 13 テ」ツ?ィテ」ツ?ェテ」ツつ凝ッツシツ?
    static typename std::enable_if<IsPrime, ll>::type inv(ll a, ll p) {
        return (a == 1 ? 1 : (1 - p*inv(p%a, a))/a + p);
    }
};

template <int M, bool IsPrime>
modulo<M, IsPrime> operator+(modulo<M, IsPrime> lhs, modulo<M, IsPrime> const& rhs) {
    lhs += rhs;
    return lhs;
}
template <int M, bool IsPrime>
modulo<M, IsPrime> operator-(modulo<M, IsPrime> lhs, modulo<M, IsPrime> const& rhs) {
    lhs -= rhs;
    return lhs;
}
template <int M, bool IsPrime>
modulo<M, IsPrime> operator*(modulo<M, IsPrime> lhs, modulo<M, IsPrime> const& rhs) {
    lhs *= rhs;
    return lhs;
}

// sw == false -> inv
template <int M>
modulo<M, true> fact(int n, bool sw = true) {
    static std::vector<modulo<M, true>> v1 = {1}, v2 = {1};
    if(n >= (int)v1.size()) {
        const int from = v1.size(), to = n + 1024;
        v1.reserve(to);
        v2.reserve(to);
        for(int i=from; i<to; ++i) {
            v1.push_back(v1.back() * modulo<M, true>(i));
            v2.push_back(v2.back() / modulo<M, true>(i));
        }
    }
    return sw ? v1[n] : v2[n];
}

template <int M>
modulo<M, true> comb(int a, int b) {
    if(b < 0 || b > a) {
        return fact<M>(0);
    }
    return fact<M>(a, true) * fact<M>(b, false) * fact<M>(a-b, false);
}


const int MOD = 1000000007;
using mod = modulo<MOD, true>;
using ll = long long;

int main() {
    int n, t;
    cin >> n >> t;
    vector<int> v(n);
    for(int i=0; i<n; ++i) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    vector<mod> ans(n);
    ans[0] = mod(1);
    for(int i=1; i<n; ++i) {
        int tmp = lower_bound(v.begin(), v.end(), v[i]-t) - v.begin();
        ans[i] = ans[i-1] * mod(i-tmp+1);
    }
    cout << ll(ans[n-1]) << endl;
}