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 <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
//#include <utility>
//#include <memory>
//#include <functional>
//#include <deque>
//#include <cctype>
//#include <ctime>
//#include <numeric>
//#include <list>
//#include <iomanip>

//#if __cplusplus >= 201103L
//#include <array>
//#include <tuple>
//#include <initializer_list>
//#include <forward_list>
//
//#define cauto const auto&
//#else

//#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

// Mod int
// const int MOD = 1000000007;
struct mint{
    ll x;
    mint():x(0){}
    mint(ll x):x((x%MOD+MOD)%MOD){}
    mint operator+=(const mint& a){ if((x+=a.x)>=MOD) x-=MOD; return *this;}
    mint operator-=(const mint& a){ if((x+=MOD-a.x)>=MOD) x-=MOD; return *this;}
    mint operator*=(const mint& a){ (x*=a.x)%=MOD; return *this;}
    mint operator+(const mint& a)const{ return mint(*this) += a;}
    mint operator-(const mint& a)const{ return mint(*this) -= a;}
    mint operator*(const mint& a)const{ return mint(*this) *= a;}
    bool operator==(const mint& a)const{ return x == a.x;}
};

static const int MAX_SIZE = 1 << 17; //segment tree ??????????????? 2^17 ??? 1.3 * 10^5

mint all[2 * MAX_SIZE - 1], part[2 * MAX_SIZE - 1]; // segment tree

//??????[a, b)??????x???????????????.
void add(int a, int b, mint x, int k = 0, int l = 0, int r = MAX_SIZE)
{
    if (a <= l && r <= b){ //[l, r)???[a, b)????????¨??????????????????????????°
        all[k] += x; //[l, r)?????¨??????????????????????????¨??????x????¶????.
    }
    else if (l < b && a < r){ //[l, r)??¨[a, b)???????????????????????°
        part[k] += mint(min(b, r) - max(a, l)) * x;  //??????????????????????????????, ??¨?????????????????????????????????????????????.
        add(a, b, x, k * 2 + 1, l, (l + r) / 2); //?????§????????????????????????.
        add(a, b, x, k * 2 + 2, (l + r) / 2, r); //???.
    }
}

mint sum(int a, int b, int k = 0, int l = 0, int r = MAX_SIZE)
{
    if (b <= l || r <= a){ //[a, b)??¨[l, r)?????¨????????????????????´???
        return mint(0);
    }
    else if (a <= l && r <= b){ //?????¨??????????????????????????°
        return (all[k] * (r - l) + part[k]);
    }
    else { //[l, r)??¨[a, b)???????????????????????°
        mint res;
        res = mint(min(b, r) - max(a, l)) * all[k]; //????????????????????¨??????????´??????????????????????, [a, b)????±?????????????????????????????????????.
        res += sum(a, b, k * 2 + 1, l, (l + r) / 2); //??????????????§???????±???????.
        res += sum(a, b, k * 2 + 2, (l + r) / 2, r); //???
        return (res);
    }
}


void mainmain(){
	int n,T;
	cin>>n>>T;
	vint v(n);
	rep(i,n) cin>>v[i];
	sort(ALL(v));
	int p = 0;
	add(0,1,mint(1));
	rep(i,n){
		while(p < n && v[p]-v[i]<=T) p++;
		add(i+1,i+2,sum(i,i+1)*mint(p-i-1));
		add(i+1, i+2, sum(i, i+1));
	}
	cout << sum(n,n+1).x << endl;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}