#include <bits/stdc++.h>
#define int long long
using namespace std;

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

const int NMAX = 5000;
const int MOD  = 2000003;

int n, k;
int v[NMAX+1];
int fact[NMAX+1];

/*
Toate numerele sunt distincte, deci de fiecare dată când alegem un șir de lungime l, vom face l - k operații.
Așadar, răspunsul la problemă este C(n,l)*(l-k), pentru orice l > k
*/

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

int fastexp(int b, int exp) {
    int ans = 1;
    while(exp) {
        if(exp % 2 == 1) ans = 1ll * (ans * b) % MOD, exp--;
        else b = 1ll * (b * b) % MOD, exp /= 2;
    }
    return ans;
}

int invmod(int x) {
    return fastexp(x, MOD - 2);
}

int c(int a, int b) {
    if (b > a) return 0;
    return 1ll * (fact[a] * invmod(fact[a - b]) % MOD) * invmod(fact[b]) % MOD;
}

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

    fout << 1ll*c(n-1, (n-1)%(k-1))%MOD;
    return 0;
}