#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 1e6 + 3;

int power(int a, int b) {
    int c = 1;
    while (b) {
        if (b % 2) {
            c = 1ll * c * a % P;
        }
        a = 1ll * a * a % P;
        b /= 2;
    }
    return c;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, k;
    std::cin >> n >> k;

    std::vector<int> a(n - k + 1);
    for (int i = 0; i < n - k + 1; ++i) {
        std::cin >> a[i];
    }

    std::vector<int> s(k), l(k), r(k);
    for (int i = 0; i < n - k; ++i) {
        int p = i % k;
        s[p] += a[i + 1] - a[i];
        l[p] = std::min(l[p], s[p]);
        r[p] = std::max(r[p], s[p]);
    }

    int cnt = 0, sum = a[0];
    for (int i = 0; i < k; ++i) {
        if (l[i] == -1) {
            sum -= 1;
        } else if (r[i] == 0) {
            ++cnt;
        }
    }

    std::vector<int> fac(n + 1), ifac(n + 1);
    fac[0] = 1;
    for (int i = 0; i < n; ++i) {
        fac[i + 1] = 1ll * fac[i] * (i + 1) % P;
    }
    ifac[n] = power(fac[n], P - 2);
    for (int i = n - 1; i >= 0; --i) {
        ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
    }

    std::cout << 1ll * fac[cnt] * ifac[sum] % P * ifac[cnt - sum] % P << "\n";

    return 0;
}