#include <iostream>
#include <fstream>
#include <unordered_map>
#include <cstring>

using namespace std;

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

const long long MOD = 2000003;
long long n, k, x, fact[100005], v[5005];

long long pow(long long x, long long p) {
    if (p == 0)
        return 1;
    if (p & 1)
        return (x * pow(x, p - 1)) % MOD;
    long long P = pow(x, p >> 1) % MOD;
    return (P * P) % MOD;
}

long long inv_mod(long long x) {
    return pow(x, MOD - 2);
}

long long aranjamente(long long n, long long k) {
    return (fact[n] * inv_mod(fact[n - k])) % MOD;
}

long long combi(long long n, long long k) {
    return (fact[n] * inv_mod(fact[n - k]) % MOD * inv_mod(fact[k])) % MOD;
}

int main() {
    fin >> n >> k;

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    fact[0] = 1;
    for (int i = 1; i <= 1e4 + 5; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    fout << combi(n - 1, (n - 1) % (k - 1));

    return 0;
}