#include <bits/stdc++.h>

using namespace std;

#define MOD 2000003

ifstream f("sandokan.in");
ofstream g("sandokan.out");

long long n, k, fact[100005];
int a[5005];


long long pow(long long x, long long p){
    if (p == 0)
        return 1;
    if (p & 1) /// daca p este impar
        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 combinari(int n,int k){
    return fact[n] * Inv_MOD(fact[n-k]) % MOD * Inv_MOD(fact[k] )% MOD;
}

int main()
{
    f >> n >> k;
    for(int i = 1; i <= n; i++) f >> a[i];

    fact[0] = 1;
    for(int i = 1; i <= 10005; i++) fact[i] = fact[i-1] * i % MOD;

    g << combinari(n-1, (n-1) % (k-1));
    return 0;
}