#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,mod=1e6+3;
int a[N],n,k;
int b[N],nxt[N],vis[N];
void ast(bool flag){
    if (flag) return;
    puts("0"),exit(0);
}
int ksm(int x,int y){
    int res=1;
    while (y){
        if (y&1) res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return res;
}
int binom(int n,int m){
    int v1=1,v2=1;
    for (int i=n-m+1;i<=n;++i) v1=1ll*v1*i%mod;
    for (int i=1;i<=m;++i) v2=1ll*v2*i%mod;
    return 1ll*v1*ksm(v2,mod-2)%mod;
}
int main(){
    // freopen("a.in","r",stdin);
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;++i) b[i]=nxt[i]=-1;
    for (int i=1;i<=n-k+1;++i) scanf("%d",&a[i]),ast(0<=a[i] && a[i]<=k);
    for (int i=1;i<n-k+1;++i){
        ast(abs(a[i]-a[i+1])<=1);
        if (a[i]==a[i+1]) nxt[i]=i+k;
        else if (a[i]==a[i+1]+1){
            ast(b[i]==-1 || b[i]==1),b[i]=1;
            ast(b[i+k]==-1 || b[i+k]==0),b[i+k]=0;
        }
        else{
            ast(b[i]==-1 || b[i]==0),b[i]=0;
            ast(b[i+k]==-1 || b[i+k]==1),b[i+k]=1;
        }
    }
    for (int i=1;i<=n;++i)
        if (!vis[i]){
            int f[2]={0,0};
            for (int j=i;j!=-1;j=nxt[j]){
                vis[j]=1;
                if (b[j]!=-1) f[b[j]]=1;
            }
            ast(f[0]+f[1]<=1);
        }
    int c[2]={0,0};
    for (int i=1;i<=k;++i){
        int f[2]={0,0};
        for (int j=i;j!=-1;j=nxt[j]) if (b[j]!=-1) f[b[j]]=1;
        ast(f[0]+f[1]<=1);
        c[0]+=f[0],c[1]+=f[1];
    }
    ast(c[1]<=a[1]);
    printf("%d\n",binom(k-c[1]-c[0],a[1]-c[1]));
    return 0;
}