#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5+3;
const ll mod  = 1e6+3;
ll i,j,p,q,n,m,k,a[maxn],l,r,b[maxn],dp[maxn],sum;
pair <long long,int> vh[maxn];
long long rsq (ll k)
{
    ll sum=0;
    while (k>=0)
    {
        sum+=b[k];
        k=(k&(k+1)) - 1;
    }
    return sum;
}
void upd (ll k, ll d)
{
    while (k<n)
    {
        b[k]+=d;
        k=k|(k+1);
    }
}
void read()
{
    freopen("inversions.in","r",stdin);
    freopen("inversions.out","w",stdout);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    read();
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>vh[i].first;
        vh[i].second=i;
    }
    sort(vh+1,vh+n+1);
    for(i=1;i<=n;i++)
    {
        if(vh[i].first!=vh[i-1].first)
            a[vh[i].second]=a[vh[i-1].second]+1;
        else a[vh[i].second]=a[vh[i-1].second];
    }
    l=1;r=2;
    upd(a[1],1);
    dp[1]=1;
    dp[0]=1;
    sum=2;
    while(r<=n)
    {
        p+=(r-l)-rsq(a[r]);//number of inversions
        upd(a[r],1);
        //cout<<p<<endl;
        if(p>k)
        {
            while(l<=r && p>k)
            {
                //cout<<l<<" uj "<<r<<" "<<p<<endl;
                sum-=dp[l-1];
                sum+=mod;
                sum%=mod;
                p-=rsq(a[l]-1);
                upd(a[l],-1);
                l++;

            }
        }
       // cout<<l<<" "<<r<<" "<<p<<endl;
        dp[r]=sum;
       // cout<<r<<" "<<dp[r]<<endl;
        sum+=dp[r];
        sum%=mod;
        r++;
    }
    cout<<dp[n];
    return 0;
}
/**
10 5
1 3 12 48 182 31 12 10 11 1
*/