#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j, r##i=k; i<=r##i; ++i)
#define ROF(i,j,k) for(int i=j, l##i=k; i>=l##i; --i)
inline int read (void) {
  int x = 0, f = 1, ch = getchar();
  while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
  while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
const int maxn = 1000005;
const int mod = 1000003;
int a[maxn], f[maxn];
bool vis[maxn];
inline int find (int x) {
  while(x != f[x]) x = f[x] = f[f[x]];
  return x;
}
inline int ksm (int a, int b) {
  int c = 1;
  while(b) {
    if(b&1) c = 1ll * c * a % mod;
    a = 1ll * a * a % mod; b >>= 1;
  } return c;
}
inline int binom (int n, int m) {
  int p = 1, q = 1;
  FOR(i,1,m) p = 1ll * p * (n - i + 1) % mod, q = 1ll * q * i % mod;
  return 1ll * p * ksm (q, mod-2) % mod;
}
int main (void) {
  int n = read(), k = read(), tot = 0;
  FOR(i,1,n-k+1) a[i] = read();
  std::iota (f+1, f+n+3, 1);
  FOR(i,1,n-k)
    if(a[i] == a[i+1]) f[find(i)] = find(i+k);
    else if(a[i] == a[i+1] + 1) f[find(i)] = find(n+2), f[find(i+k)] = find(n+1);
    else f[find(i)] = find(n+1), f[find(i+k)] = find(n+2);
  FOR(i,1,k) if(find(i) == find(n+2)) -- a[1]; else if(find(i) != find(n+1) && !vis[find(i)]) vis[find(i)] = 1, ++ tot;
  printf("%d\n", binom (tot, a[1]));
  return 0;
}