# include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e6;
long long segm[MAXN];
void update(long long v, long long from, long long to, long long x, long long delta)
{
    if(from==to)
    {
        segm[v] += delta;
        return ;
    }
    long long mid = (from+to)/2;
    if(x<=mid)update(2*v,from,mid,x,delta);
    else
        update(2*v+1,mid+1,to,x,delta);
    segm[v] = segm[2*v]+segm[2*v+1];
}
long long query(long long v, long long from, long long to, long long l, long long r)
{
 //  cout<<v<<" "<<from<<" "<<to<<" "<<l<<" "<<r<<endl;
    if(l > r) return 0;
    if(l<=from&&to<=r)return segm[v];
    long long ans = 0;
    long long mid = (from+to)/2;
    if(l<=mid)ans+=query(2*v,from,mid,l,r);
    if(r>mid)ans+=query(2*v+1,mid+1,to,l,r);
   // cout << v<< " ::: "<< ans<<endl;
    return ans;

}
const long long MOD = 1e6+3;
long long ANS[MAXN];
long long pref[MAXN];
long long a[MAXN];

pair <long long,long long> p[MAXN];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen ("inversions.in","r",stdin);  freopen ("inversions.out","w",stdout);
    long long n,k;
    cin>>n>>k;
    long long i,j;
    for(i = 1;i<=n;i++)
    {
        cin>>p[i].first;
        p[i].second=  i;
    }
    sort(p+1,p+n+1);
    long long id = 0;
    for(i = 1;i<=n;i++)
    {
        if(p[i].first!=p[i-1].first)id++;
        a[p[i].second] = id;
    }

    long long l = 1;
    ANS[0]  = 1;
    ANS[1] = 1;
    pref[1] = 2;
    pref[0] = 1;
    update(1,1,n,a[1],1);
    long long curr = 0;
    for(i = 2;i<=n;i++)
    {
        curr = curr + query(1,1,n,a[i]+1,n);
        update(1,1,n,a[i],1);
       // cout<<curr<<endl;
        while(curr > k)
        {
            curr = curr - query(1,1,n,1,a[l]-1);
           // cout<<l<<" then " << curr << endl;
            update(1,1,n,a[l],-1);
            l++;
        }
        ANS[i] = (MOD+pref[i-1] - (l-2 >= 0 ? pref[l-2] : 0))%MOD;
      //  cout<<i<<": "<<l<<" "<<curr<<" --> "<<ANS[i]<<endl;
        pref[i] = (pref[i-1]+ANS[i])%MOD;
    }
    cout<<ANS[n]<<endl;
}