#include <bits/stdc++.h>
#define mod 2000003
using namespace std;

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

int fact[5001];

long long rptl(int b,int e){

    long long rez=1;
    while(e>0)
    {
        if(e%2==0)
        {
           b=(1LL*b*b)%mod;
           e/=2;
        }
        else
        {
            rez=(1LL*rez*b)%mod;
            --e;
        }
    }
    return rez;
}
int c(int n,int k){
    return 1LL*((fact[n]%mod)*(rptl(fact[k],mod-2)%mod)*(rptl(fact[n-k],mod-2)%mod))%mod;
}
int main()
{
    int n,i,k,nr;
    in>>n>>k;
    for(i=1;i<=5001;++i)
        in>>nr;
    fact[0]=fact[1]=1;
    for(i=2;i<=n;++i)
        fact[i]=(fact[i-1]*i)%mod;

    out<<c((n-1),(n-1)%(k-1));
    return 0;
}