#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1000010,MOD=1e6+3;
int s[N],p[N],v[N];
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=(long long)res*a%MOD;
        a=(long long)a*a%MOD;
        b>>=1;
    }   
    return res;
}
int C(int a,int b){
    int fa=1,fb=1,fab=1;
    for(int i=1;i<=a;i++) fa=(long long)fa*i%MOD;
    for(int i=1;i<=b;i++) fb=(long long)fb*i%MOD;
    for(int i=1;i<=a-b;i++) fab=(long long)fab*i%MOD;
    
    return (long long)fa*qmi(fb,MOD-2)*qmi(fab,MOD-2)%MOD;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n-m+1;i++) cin>>s[i];
    for(int i=0;i<n;i++) p[i]=i,v[i]=-1;
    
    for(int i=0,j=m;i<n-m;i++,j++){
        if(s[i]==s[i+1])
        p[find(j)]=find(i);
    }
    
    for(int i=0,j=m;i<n-m;i++,j++){
        if(s[i]>s[i+1]){
            v[find(i)]=1,v[find(j)]=0;
        }
        else if(s[i]<s[i+1]){
            v[find(i)]=0,v[find(j)]=1;
        }
    }
    int c0=0,c1=0;
    for(int i=0;i<m;i++){
        int t=v[find(i)];
        if(t==0) c0++;
        if(t==1) c1++;
    }
    cout<<C(m-c0-c1,s[0]-c1);
    
    return 0;
}