#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include "lib.h"
#endif
#define rep(i, min, max) for(int i = (min); i <= (max); ++i)
#define nrep(i, max, min) for(int i = (max); i >= (min); --i)
#define reads(str) (scanf("%s", str + 1), strlen(str + 1))
#define case() int Ts = read(); rep(T, 1, Ts)
#define putf(flag) puts((flag) ? "YES" : "NO")
#define put(x) printf("%d ", x)
#define putl(x) printf("%lld ", x)
#define endl() putchar('\n')
using namespace std;

typedef long long ll;
inline int read()
{
    int now=0; bool nev=false; char c=getchar();
    while(c<'0' || c>'9') { if(c=='-') nev=true; c=getchar(); }
    while(c>='0' && c<='9') { now=(now<<1)+(now<<3)+(c&15); c=getchar(); }
    return nev?-now:now;
}

const int N = 1e6 + 10;
const ll mod = 1e6 + 3;

int a[N];
int s[N], pre[N];
ll A[N], nA[N];

ll fpow(ll a, ll k){
    ll res = 1;
    while(k){
        if(k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

void init(int n){
    A[0] = 1;
    rep(i, 1, n) A[i] = A[i - 1] * i % mod;
    nA[n] = fpow(A[n], mod - 2);
    nrep(i, n, 1) nA[i - 1] = nA[i] * i % mod;
}

inline ll C(int tot, int cur){
    return A[tot] * nA[cur] % mod * nA[tot - cur] % mod;
}

int main() {
    int n = read(), k = read();
    init(n + 1);
    rep(i, 1, n - k + 1) s[i] = read();
    rep(i, 1, n) a[i] = 2;
    rep(i, 1, n - k) {
        pre[i] = s[i + 1] - s[i];
        a[i + k] = a[i] + pre[i];
        if(s[i] == s[i + 1]) continue;
        if(a[i] == 2 && pre[i] == 1) a[i] = 0, a[i + k] = 1;
        if(a[i] == 2 && pre[i] == -1) a[i] = 1, a[i + k] = 0;
        if(a[i + k] != 0 && a[i + k] != 1) puts("0"), exit(0);
    }
    nrep(i, n - k, 1) a[i] = a[i + k] - pre[i];
    // parray(a, n);
    int sum = s[1], cnt = 0;
    rep(i, 1, k) {
        if(a[i] == 2) cnt ++;
        else sum -= a[i];
    }
    putl(C(cnt, sum));
}