#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
const int mod = 1e6 + 3;

int n, K, cnt;
int a[N], ans[N], fac[N], inv[N];

int qpow(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1) {
            res = 1ll * res * x % mod;
        }
        x = 1ll * x * x % mod;
        y >>= 1;
    }
    return res;
}

int C(int x, int y) {
    if (x < y) {
        return 0;
    }
    return 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod;
}

int main() {
    // freopen("a.in", "r", stdin);
    // freopen("a.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> K;
    fac[0] = 1;
    for (int i = 1; i <= K; i++) {
        fac[i] = 1ll * fac[i - 1] * i % mod;
    }
    inv[K] = qpow(fac[K], mod - 2);
    for (int i = K; i >= 1; i--) {
        inv[i - 1] = 1ll * inv[i] * i % mod;
    }
    for (int i = K; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = K; i < n; i++) {
        ans[i + 1] = ans[i + 1 - K] + a[i + 1] - a[i];
    }
    for (int i = 0; i < K; i++) {
        ans[i] = -1;
    }
    for (int i = K + 1; i <= n; i++) {
        if (ans[i] == 1) {
            if (ans[i % K] == 1) {
                cout << "0\n";
                return 0;
            }
            ans[i % K] = 0;
        }
        else if(ans[i] == -1) {
            if (ans[i % K] == 0) {
                cout << "0\n";
                return 0;
            }
            ans[i % K] = 1;
        }
        else if(ans[i]) {
            cout << "0\n";
            return 0;
        }
    }
    for (int i = 0; i < K; i++) {
        if (ans[i] == -1) {
            cnt++;
        }
        else if(ans[i] == 1) {
            a[K]--;
        }
    }
    cout << C(cnt, a[K]) << '\n';

    return 0;
}