#include<bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define pb push_back
using namespace std;
typedef pair<int,int> pii;

const int mod=1e6+3;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){if(base==0)return 0;int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}

const int maxn=1e5+10;

int a[maxn],n,q,tree[maxn*4];
ll k;

void build(int x,int l,int r){

    if(l==r){
        tree[x]=0;
        return;
    }
    int mid=(l+r)/2;

    build(x*2,l,mid);
    build(x*2+1,mid+1,r);

    tree[x]=(tree[x*2]+tree[x*2+1]);
}
void update(int x,int l,int r,int id,int val){

    if(l>id || r<id)return;
    if(l==r){
        tree[x]+=val;
        return;
    }
    int mid=(l+r)/2;

    update(x*2,l,mid,id,val);
    update(x*2+1,mid+1,r,id,val);

    tree[x]=(tree[x*2]+tree[x*2+1]);
}
int query(int x,int l,int r,int lp,int rp){
    if(l>rp || r<lp)return 0;
    if(l>=lp && r<=rp)return tree[x];
    int mid=(l+r)/2;
    return (query(x*2,l,mid,lp,rp)+query(x*2+1,mid+1,r,lp,rp));
}
int dp[maxn],pdp[maxn];
int main(){

    freopen("inversions.in","r",stdin);
    freopen("inversions.out","w",stdout);


    scanf("%d %lld",&n,&k);
    vector<int>cand;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        cand.pb(a[i]);
    }
    sort(cand.begin(),cand.end());
    cand.resize( unique(cand.begin(),cand.end())-cand.begin() );
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(cand.begin(),cand.end(),a[i])-cand.begin();
        a[i]++;
        ///printf("%d ",a[i]);
    }
    ///printf(" NIZ\n");

    build(1,1,n);
    dp[0]=1;
    pdp[0]=1;
    int curr=1;
    ll cinv=0;
    for(int i=1;i<=n;i++){

        cinv+=(ll)query(1,1,n,a[i]+1,n);
        update(1,1,n,a[i],1);
        ///printf("%d %lld  INV\n",i,cinv);
        while(k<cinv){
            cinv-=(ll)query(1,1,n,1,a[curr]-1);
            update(1,1,n,a[curr],-1);
            curr++;
            ///printf("%d %lld  INV\n",i,cinv);
        }

        ///printf("%d %lld aA\n",curr,cinv);

        if(curr-2>=0)dp[i]=sub(pdp[i-1],pdp[curr-2]);
        else dp[i]=pdp[i-1];

        pdp[i]=add(pdp[i-1],dp[i]);
    }

    printf("%d\n",dp[n]);

return 0;
}