#include <iostream>
#include <cstdio>
#include <cstring>
#define mod 1000003
using namespace std;
int Qpow(int a,int p){
	if (p==0)return 1;
	int t=Qpow(a,p/2);
	t=1ll*t*t%mod;
	if (p&1)t=1ll*t*a%mod;
	return t;
}
int n,k,a[1000005];
int c[1000005];
void upd(int x){
	if (x>k&&c[x-k]==-1){
		c[x-k]=1-c[x];
		upd(x-k);
	}
	if (x<=n-k&&c[x+k]==-1){
		c[x+k]=1-c[x];
		upd(x+k);
	}
	return;
}
int C(int n,int m){
	if (m<0||m>n)return 0;
	int ans=1;
	for (int i=n-m+1;i<=n;i++)ans=1ll*ans*i%mod;
	int fac=1;
	for (int i=1;i<=m;i++)fac=1ll*fac*i%mod;
	return 1ll*ans*Qpow(fac,mod-2)%mod;
}
int main(){
	cin>>n>>k;
	for (int i=1;i<=n-k+1;i++)scanf("%d",&a[i]);
	memset(c,-1,sizeof(c));
	for (int i=1;i<=n-k;i++){
		if (a[i]<a[i+1])c[i]=0,c[i+k]=1;
		if (a[i]>a[i+1])c[i]=1,c[i+k]=0;
	}
	for (int i=1;i<=n;i++)
		if (c[i]!=-1)upd(i);
	int x=a[1],y=0;
	for (int i=1;i<=k;i++){
		if (c[i]==1)x--;
		if (c[i]==-1)y++;
	}
	cout<<C(y,x)<<endl;
	return 0;
}