#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define NMAX 5000
#define MMAX 26
#define MOD 2000003

using namespace std;

ifstream fin("sandokan.in");
ofstream fout("sandokan.out");

int n, k, x;
ull fact[NMAX + 2];

ull fast_expo(ull a, ull b) {
    ull p = 1;
    while (b) {
        if (b & 1) {
            p = (p * a) % MOD;
        }
        a = (a * a) % MOD;
        b >>= 1;
    }
    return p;
}

ull comb(int n, int k) {
    if (k > n || k < 0) {
        return 0;
    }
    if (k == 0 || k == n) {
        return 1;
    }
    if (k == 1) {
        return n;
    }
    ull rez = fact[n];
    ull inv1 = fast_expo(fact[n - k], MOD - 2);
    ull inv2 = fast_expo(fact[k], MOD - 2);
    rez = (rez * inv1) % MOD;
    rez = (rez * inv2) % MOD;
    return rez;
}

void precalc() {
    fact[0] = fact[1] = 1;
    for (int i = 2; i <= NMAX; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    precalc();
    fin >> n >> k;
    for (int i = 1; i <= n; i++) {
        fin >> x;
    }

    fout << comb(n - 1, (n - 1) % (k - 1));
    return 0;
}