#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int N = 1e6 + 10, MOD = 1e6 + 3;

int n, k, a[N], b[N];

void upd(int i) {if (i - k >= 1 && b[i - k] == -1) b[i - k] = b[i], upd(i - k);}

ll inv(ll base, int e = MOD - 2) {
    ll res = 1;
    while (e) {
        if (e & 1) res = res * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    return res;
}

int C(int n, int m) {
    ll a = 1, b = 1;
    for (int i = m + 1; i <= n; i++) a = a * i % MOD;
    for (int i = n - m; i; i--) b = b * i % MOD;
    return a * inv(b) % MOD;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= n - k + 1; i++) cin >> a[i];
    fill(b + 1, b + n + 1, -1);
    for (int i = 1; i <= n - k; i++) {
        if (a[i] > a[i + 1]) b[i] = 1, b[i + k] = 0;
        else if (a[i] < a[i + 1]) b[i] = 0, b[i + k] = 1;
    }
    for (int i = k + 1; i <= n; i++) if (b[i] != -1) upd(i);
    int tot = 0, cnt = a[1];
    for (int i = 1; i <= k; i++) {
        if (b[i] == 1) cnt--;
        else if (b[i] == -1) tot++;
    }
    cout << C(tot, cnt);
    return 0;
}