#include <fstream>
#define mod 2000003
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int n,k,x,i;

int fact(int n) {
    long long p=1;
    for (int i=2;i<=n;i++)
        p=p*i%mod;
    return p;
}

int putere(int a,int n) {
    long long p=1;
    while (n!=0) {
        if (n%2!=0)
            p=p*a%mod;
        a=1LL*a*a%mod;
        n/=2;
    }
    return p;
}

int comb(int n,int k) {
    return 1LL*fact(n)*putere(fact(k),mod-2)%mod*putere(fact(n-k),mod-2)%mod;
}

int main() {
    fin>>n>>k;
    for (i=1;i<=n;i++)
        fin>>x;
    fout<<comb(n-1,(n-1)%(k-1));
    return 0;
}