#include <bits/stdc++.h>
#define M 2000003
using namespace std;
ifstream f("sandokan.in");
ofstream g("sandokan.out");
long long fct[5001];
long long put(long long a, long long n)
{
    long long r=1;
    while(n)
    {
        if(n%2)
            r=(r*a)%M;
        n/=2;
        a=(a*a)%M;
    }
    return r;
}
long long C(long long n, long long k)
{
    long long p1,p2;
    p1=fct[n];
    p2=(fct[n-k]*fct[k])%M;
    p2=put(p2,M-2);
    return (p1*p2)%M;
}
int main()
{long long n,k,i;
f>>n>>k;
fct[0]=1;
for(i=1;i<=n;i++)
    fct[i]=(i*fct[i-1])%M;
g<<C(n-1,(n-1)%(k-1));

    return 0;
}