#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
const int N=1e6+3,mod=1e6+3;
int n,k,a[N],fac[N],inv[N];
int fa[N],num[N],col[N];
int ksm(int x,int y)
{
    int res=1;
    for(;y;y>>=1)
    {
        if(y&1) res=1ll*res*x%mod;
        x=1ll*x*x%mod;
    }
    return res;
}
void pre()
{
    fac[0]=1;
    for(int i=1;i<N;i++) fac[i]=1ll*i*fac[i-1]%mod;
    inv[N-1]=ksm(fac[N-1],mod-2);
    for(int i=N-1;i;i--) inv[i-1]=1ll*i*inv[i]%mod;
}
int C(int x,int y) {if(y<0||y>x) return 0;return 1ll*fac[x]*inv[x-y]%mod*inv[y]%mod;}
int Find(int x) {return x==fa[x]?x:fa[x]=Find(fa[x]);}
void merge(int x,int y)
{
    x=Find(x),y=Find(y);
    if(x==y) return;
    if(num[x]<num[y]) swap(x,y);
    if(~col[x]&&~col[y]&&col[x]!=col[y]) puts("0"),exit(0);
    if(!~col[x]) col[x]=col[y];
    num[x]+=num[y],fa[y]=x;
}
void upd(int x,bool y)
{
    x=Find(x);
    if(~col[x]&&col[x]!=y) puts("0"),exit(0);
    col[x]=y;
}
int main()
{
    pre();
    memset(col,-1,sizeof(col));
    n=read(),k=read();
    for(int i=1;i<=n;i++) fa[i]=i,num[i]=1;
    for(int i=1;i<=n-k+1;i++) a[i]=read();
    for(int i=1;i<n-k+1;i++)
        if(a[i]==a[i+1]) merge(i,i+k);
        else if(abs(a[i]-a[i+1])>1) return puts("0"),0;
        else upd(i,a[i]>a[i+1]),upd(i+k,a[i]<a[i+1]);
    int t1=0,t2=0;
    for(int i=1;i<=k;i++)
        t1+=(col[Find(i)]==1),t2+=!~col[fa[i]];
    printf("%d\n",C(t2,a[1]-t1));
    return 0;
}