#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000003; // 10^6 + 3
ll modpow(ll a, ll e){
ll r=1;
while(e){
if(e&1) r = (r*a)%MOD;
a = (a*a)%MOD;
e >>= 1;
}
return r;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,K;
if(!(cin>>N>>K)) return 0;
int M = N - K + 1;
vector<int> S(M+1);
for(int i=1;i<=M;i++) cin>>S[i];
if(M==0){
// K > N? but constraints say K <= N. fallback
cout<<0<<"\n";
return 0;
}
// differences d[i] = S[i+1]-S[i], for i = 1..M-1
vector<int> d(M+1,0);
for(int i=1;i<=M-1;i++) d[i] = S[i+1] - S[i];
int forcedOnes = 0, forcedZeros = 0, freeChains = 0;
for(int r=1; r<=K; r++){
// traverse positions r, r+K, r+2K, ...
int pos = r;
int c = 0; // c_t
bool impossible = false;
bool hasPos1 = false; // c_t == 1
bool hasNeg1 = false; // c_t == -1
// t=0 (pos=r) => c=0 check
if(abs(c) >= 2) impossible = true;
if(c == 1) hasPos1 = true;
if(c == -1) hasNeg1 = true;
// advance while pos <= N-K (i.e., there exists d[pos])
while(pos <= N - K){
// step: c += d[pos], move to pos+K
c += d[pos];
pos += K;
if(abs(c) >= 2){ impossible = true; break; }
if(c == 1) hasPos1 = true;
if(c == -1) hasNeg1 = true;
}
if(impossible){ cout << 0 << '\n'; return 0; }
if(hasPos1 && hasNeg1){ cout << 0 << '\n'; return 0; }
if(hasPos1) forcedZeros++; // c==1 forces x_r = 0
else if(hasNeg1) forcedOnes++; // c==-1 forces x_r = 1
else freeChains++; // all c==0 -> free
}
int need = S[1] - forcedOnes;
if(need < 0 || need > freeChains){ cout << 0 << '\n'; return 0; }
// compute C(freeChains, need) modulo MOD
int n = freeChains;
int k = need;
// precompute factorials up to n
vector<ll> fact(n+1,1), invfact(n+1,1);
for(int i=1;i<=n;i++) fact[i] = (fact[i-1]*i)%MOD;
invfact[n] = modpow(fact[n], MOD-2);
for(int i=n;i>=1;i--) invfact[i-1] = (invfact[i]*i)%MOD;
ll ans = fact[n];
ans = ans * invfact[k] % MOD;
ans = ans * invfact[n-k] % MOD;
cout << ans % MOD << '\n';
return 0;
}
