#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 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 combinari(int n,int k)
{   return  fact[n]*inversmodular(fact[n-k])%MOD*inversmodular(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<=1e4+5;i++) fact[i]=fact[i-1]*i%MOD;
    g << combinari(n-1,(n-1)%(k-1));
    return 0;
}