#include <iostream>
#include <fstream>
#define MOD 2000003
using namespace std;
ifstream f("sandokan.in");
ofstream g("sandokan.out");
int fact[5005],n,k;
int invers(int x,int y)
{
    int sol=1;
    while(y)
    {
        if(y&1)sol=(1LL*sol*x)%MOD;
        x=(1LL*x*x)%MOD;
        y>>=1;
    }
    return sol;
}
void factorial()
{
    fact[0]=1; fact[1]=1;
    for(int i=2;i<=n;i++)
        fact[i]=(1LL*fact[i-1]*i)%MOD;
}
int comb(int n,int k)
{
    if(k>n)return 0;
    if(k==n)return 1;
    if(!n||!k)return 1;
    return 1LL*fact[n]*invers(1LL*fact[k]*fact[n-k]%MOD,MOD-2)%MOD;
}
int main()
{
    f>>n>>k;
    factorial();
    g<<comb(n-1,(n-1)%(k-1));
    return 0;
}