#include <fstream>

using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
long long n, mod=2000003, i, k, a;
long long ans, f[50001];
long long invMod(long long b)
{
    int put=mod-2;
    long long p=1;
    while(put)
    {
        if(put%2==1)
            p=(p*b)%mod;
        b=(b*b)%mod;
        put/=2;
    }
    return p;
}
long long combinari(int n, int k)
{
    if(n<k)
        return 0;
    return (f[n]*invMod(f[n-k]*f[k]%mod))%mod;
}
int main()
{
    fin>>n>>k;
    for(i=1; i<=n; i++)
        fin>>a;
    f[0]=f[1]=1;
    int p=(n-1)%(k-1);
    for(i=1; i<=5000; i++)
        f[i]=(f[i-1]*i)%mod;
    ans=combinari(n-1, p)%mod;
    fout<<ans;
    return 0;
}