map<int,int>mp;
void solve(){
    mp.clear();
    int n=read(),cnt=0;
    string s;
    cin>>s;
    for(int i=0;i<n-1;i++){
        int x=s[i]+s[i+1]*1000;
        // cout<<x<<" ";
        if(mp[x]==0)cnt++,mp[x]=1;
    }
    // cout<<'\n';
    cout<<cnt<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

int b[N];
void solve(){
    int n=read(),k=read(),ans=1;
    for(int i=1;i<=n;i++){
        a[i].x=read();
        a[i].id=i;
    }
    for(int i=1;i<=n;i++) b[i]=read();
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++){
        if(abs(a[i].x-b[i])>k){
            ans=-1;
            break;
        }
        else a[i].ans=b[i];
    }
    if(ans<0)cout<<"-1\n";
    else {
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++){
            cout<<a[i].ans<<' ';
        }
        cout<<'\n';
    }
    // puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

map<int,int>mp;
void solve(){
    mp.clear();
    int n=read(),odd=0,even=0,minn=inf;
    for(int i=1;i<=n;i++){
        int x=read();
        if(x%2&&mp[x]==0)odd++;
        else if(mp[x]==0)even++;
        mp[x]++;
        minn=min(x,minn);
    }
    puts((minn%2==1&&odd>0)||(minn%2==0&&odd==0)?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

int a[N];
void solve(){
    int n=read(),maxx=-1,re=-1;
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(i!=1&&maxx<a[i]){
            maxx=a[i];
            re=i;
        }
    }
    if(n==1){
        cout<<a[1]<<'\n';
        return ;
    }
    if(n==2){
        cout<<a[2]<<" "<<a[1]<<'\n';
        return ;
    }
    int left=-1,right=-1;
    if(re==n){
        right=n;
        left=n;
        for(int i=n-1;i>=1;i--){
            if(a[i]>a[1]){
                left=i;
            }else break;
        }
    }
    else {
        right=re-1;
        left=re-1;
        for(int i=re-2;i>=1;i--){
            if(a[i]>a[1]){
                left=i;
            }else break;
        }
    }
    for(int i=right+1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    for(int i=right;i>=left;i--){
        cout<<a[i]<<" ";
    }
    for(int i=1;i<=left-1;i++){
        cout<<a[i]<<" ";
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

int p[N],d[N],cnt[N]; //存储每个点的祖宗节点
map<PII,int>mp;
int find(int x) {    // 返回x的祖宗节点
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void solve(){
    int n=read();
    mp.clear();
    for (int i = 1; i <= n; i ++ ) p[i] = i, cnt[i]=0, d[i]=0;  // 初始化，假定节点编号是1~n
    for(int i=1;i<=n;i++){
        int x=read();
        if(mp[{i,x}]==0){
            mp[{i,x}]++;
            mp[{x,i}]++;
            d[x]++;
            d[i]++;
        }
        p[find(i)] = find(x);  // 合并a和b所在的两个集合：
    }
    for(int i=1;i<=n;i++){
        int pa=find(i);
        if(cnt[pa]==0)cnt[pa]=1;
        cnt[pa]+=max(abs(2-d[i]),0);
    }

    int minn=0,maxx=0;
    for(int i=1;i<=n;i++){
        if(cnt[i]>0)maxx++;
        if(cnt[i]>1)minn++;
    }
    cout<<min(maxx-minn+1,maxx)<<" "<<maxx<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

#define int long long
int qmi(int m, int k, int p){
    int res = 1 % p, t = m;
    while (k){
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
void solve(){
    int n=read(),m=read();
    map<int,int>mp;
    vector<int>a(n);
    for(int i=0;i<n;i++)a[i]=read();
    sort(a.begin(),a.end());
    for(int x:a){
        mp[x]++;
    }
    a.resize(n=unique(a.begin(),a.end())-a.begin());
    int c=1,ans=0;
    for(int i=0,j=0;i<n;){
        while(j<n&&a[j]<a[i]+m)c=c*(mp[a[j++]])%mod;
        if(j-i==m)(ans+=c)%=mod;
        c=c*qmi(mp[a[i++]],mod-2,mod)%mod;
    }
    cout<<ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}