#include <bits/stdc++.h>

constexpr int mod = 1e6 + 3;
int add(int a, int b) {
    return a + b - mod * (a + b >= mod);
}
int mul(int a, int b) {
    return a * 1ULL * b % mod;
}
int power(int b, int e) {
    int r = 1;
    for (; e > 0; e >>= 1) {
        if (e & 1) {
            r = mul(r, b);
        }
        b = mul(b, b);
    }
    return r;
}

int fuck(int n) {
    int r = 1;
    for (int i = 1; i <= n; i++) {
        r = mul(r, i);
    }
    return r;
}
int C(int n, int k) {
    return mul(fuck(n), power(mul(fuck(n - k), fuck(k)), mod - 2));
}

void zero() {
    std::cout << 0 << std::endl;
    exit(0);
}

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;
    std::vector<int> input(n - k + 1);
    for (int& i : input) {
        std::cin >> i;
    }

    std::vector<int> cum(n, -1);
    int ans = 0;
    for (int i = 0; i < n - k; i++) {
        if (cum[i] == -1) {
            if (input[i] != input[i + 1]) {
                cum[i] = input[i] > input[i + 1];
                cum[i + k] = input[i] < input[i + 1];
                for (int j = i - k; j >= 0; j -= k) {
                    cum[j] = cum[j + k] + input[j] - input[j + 1];
                    if (cum[j] < 0 || cum[j] > 1) {
                        std::cerr << "fuck3 \n";
                        zero();
                    }
                }
                for (int j = i + 2 * k; j < n; j += k) {
                    cum[j] = cum[j - k] - input[j - k] + input[j - k + 1];
                    if (cum[j] < 0 || cum[j] > 1) {
                        std::cerr << "fuck4 \n";
                        zero();
                    }
                }
            }
        }
    }
    std::vector<int> dlt(input.size(), 0);
    for (int i = 0; i < n; i++) {
        if (cum[i] == 1) {
            dlt[std::max(0, i - k + 1)]--;
            if (i + 1 < input.size()) {
                dlt[i + 1]++;
            }
        }
    }

    for (int i = 0, c = 0; i < input.size(); i++) {
        c += dlt[i];

        input[i] += c;
    }
    if (!std::all_of(input.begin(), input.end(), std::bind(std::equal_to<int>(), std::placeholders::_1, input.front()))) {
        std::cerr << "fuck2 \n";
        zero();
    }
    int cnt = 0;
    for (int i = 0; i < k; i++) {
        cnt += cum[i] == -1;
    }
    int cnt2 = input[0];
    if (cnt2 < 0 || cnt2 > cnt) {
        std::cerr << "fuck1 \n";
        zero();
    }
    ans = C(cnt, cnt2);

    ans %= mod;
    std::cout << ans << "\n";

    return 0;
}