#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],i,m,sol,nr,v[5005];


long long putere(long long x, long long p)
{
    if (p==0)
        return 1;

    if (p&1)
        return x*putere(x,p-1)%MOD;

    long long P=putere(x,p>>1)%MOD;
    return P*P%MOD;
}

long long inversmodular(long long x)
{
    return putere(x,MOD-2);
}

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

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


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

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


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


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






    return 0;
}