有N(2<=N<=600000)块砖，要搭一个N层的塔，要求：如果砖A在砖B上面，那么A不能比B的长度+D要长。问有几种方法,输出 答案 mod 1000000009的值.

输入格式：

第一行： N，D 第二行： N个数，表示每块砖的长度。

输出格式：

方案数，输出要mod 1000000009

输入样例#1：

4 1
1 2 3 100

输出样例#1：

4

乘法原理

#include
#include
#include
#include
#define lli long long int
#include
using namespace std;
const int MAXN=;
const int mod=;
int read(int & n)
{
char c='.';int x=,flag=;
while(c<''||c>'')
{c=getchar(); if(c=='-')flag=; }
while(c>=''&&c<='') {x=x*+(c-);c=getchar();} if(flag==)n=-x;else n=x; } int n,d; int a[MAXN]; lli ans=; int top=; int maxn=; int main() { read(n);read(d); for(int i=;i<=n;i++) read(a[i]); sort(a+,a+n+); for(int i=;i<=n;i++) { while(a[i]>a[top]+d)
{
top++;
}
ans=ans*(i-top+);
ans=ans%mod;
}
//printf("%d",ans);
cout<<ans;
return ;
}