#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5,mod=1e6+3;
int c[N],a[N],fac[N];
struct DSU{
	int fa[N];
	void init(int n){
		for(int i=1;i<=n;i++){
			fa[i]=i;
		}
	}
	int find(int x){
		if(x==fa[x]) return x;
		return fa[x]=find(fa[x]);
	}
	void merge(int x,int y){
		int fx=find(x),fy=find(y);
		fa[fx]=fy;
	}
} dsu;
int qpow(int a,int n){
	if(n==0) return 1;
	int x=qpow(a,n/2);
	return (ll)x*x%mod*(n%2?a:1)%mod;
}
int inv(int x){
	return qpow(x,mod-2);
}
int main(){
	int n,k;cin>>n>>k;
	for(int i=1;i<=n-k+1;i++){
		cin>>c[i];
	}
	memset(a,-1,sizeof a);
	dsu.init(n);
	for(int i=2;i<=n-k+1;i++){
		if(c[i]==c[i-1]){
			dsu.merge(i-1,i+k-1);
		}
		if(c[i]>c[i-1]){
			a[i-1]=0,a[i+k-1]=1;
		}
		if(c[i]<c[i-1]){
			a[i-1]=1,a[i+k-1]=0;
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i]!=-1) a[dsu.find(i)]=a[i];
	}
	for(int i=1;i<=n;i++){
		a[i]=a[dsu.find(i)];
	}
	int tot=0,val=c[1];
	for(int i=1;i<=k;i++){
		if(a[i]==-1) tot++;
		if(a[i]==1) val--;
	}
	fac[0]=1;
	for(int i=1;i<=n;i++){
		fac[i]=(ll)fac[i-1]*i%mod;
	}
	cout<<(ll)fac[tot]*inv(fac[val])%mod*inv(fac[tot-val])%mod;
	
}