#include<iostream>
#include<cstdio>
#define N 1000000
#define mod 1000003
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int fast_pow(int a,int b)
{
    int res=1,mul=a;
    while (b)
    {
	if (b&1) res=1ll*res*mul%mod;
	mul=1ll*mul*mul%mod,b>>=1;
    }
    return res;
}
int n,k,a[N+1],s[N+1],fac[N+1],invfac[N+1];
bool used[N+1],used2[N+1];
int C(int x,int y)
{
    if (x<y) return 0;
    return 1ll*fac[x]*invfac[y]%mod*invfac[x-y]%mod;
}
int main()
{
    int cnt,cnt2=0;
    fac[0]=1;
    for (int i=1;i<=N;++i) fac[i]=1ll*fac[i-1]*i%mod;
    invfac[N]=fast_pow(fac[N],mod-2);
    for (int i=N-1;i>=0;--i) invfac[i]=1ll*invfac[i+1]*(i+1)%mod;
    n=read(),k=read();
    for (int i=1;i<=n-k+1;++i) a[i]=read(),s[i+k-1]=s[i-1]+a[i];
    for (int i=0;i<=n-1;++i)
    {
	if (i%k!=k-1)
	{
	    if (s[i]+1==s[i+1]) used[i%k]=1;
	    if (s[i]-1==s[i+1]) used2[i%k]=1;
	}
	else
	{
	    if (s[i]+1==s[i+1]-a[1]) used[i%k]=1;
	    if (s[i]-1==s[i+1]-a[1]) used2[i%k]=1;
	}
    }
    cnt=a[1];
    for (int i=0;i<=k-1;++i)
    {
	if (used2[i]) cnt--;
	else if (!used[i]) cnt2++;
    }
    printf("%d\n",C(cnt2,cnt));
    return 0;
}