#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;
struct DSU{
vi p;
DSU(int n):p(n,-1){}
int find(int x){
if(p[x]<0) return x;
return p[x]=find(p[x]);
}
bool unite(int x, int y){
x=find(x),y=find(y);
if(x==y) return false;
if(p[x]>p[y]) swap(x,y);
p[x]+=p[y],p[y]=x;
return true;
}
};
const int MOD=1e6+3;
int mul(int a, int b){
return int(1LL*a*b%MOD);
}
int binpow(int a, int k){
int r=1;
while(k){
if(k&1) r=mul(r,a);
a=mul(a,a),k/=2;
}
return r;
}
int choose(int n, int k){
if(k<0||n<0||n-k<0) return 0;
int ans=1,ans2=1;
forn(i,k){
ans=mul(ans,n-i);
ans2=mul(ans2,i+1);
}
return mul(ans,binpow(ans2,MOD-2));
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,k;
cin>>n>>k;
vi s(n-k+1);
forn(i,n-k+1) cin>>s[i];
vi x(n,-1);
DSU dsu(n);
forn(i,n-k){
int diff=s[i]-s[i+1];
if(diff==1) x[i]=1,x[i+k]=0;
else if(diff==-1) x[i]=0,x[i+k]=1;
else if(diff==0) dsu.unite(i,i+k);
else assert(false);
}
forn(i,n){
int p=dsu.find(i);
if(x[p]==-1) x[p]=x[i];
}
forn(i,n){
int p=dsu.find(i);
if(x[i]==-1) x[i]=x[p];
}
int a=0,b=s[0];
forn(i,k){
if(x[i]==-1) a++;
else if(x[i]==1) b--;
}
cout<<choose(a,b)<<'\n';
return 0;
}
