#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
const unsigned long long mod=2000003;
unsigned long long n,k,f[5001];
void _read()
{
    ifstream f("sandokan.in");
    f>>n>>k;
    f.close();

}

void _factorial()
{

    f[0]=1;
    for(unsigned long long i=1;i<=5001;++i)

        f[i]=((f[i-1]%mod)*(i%mod))%mod;

}

unsigned long long _exp(unsigned long long a, unsigned long long b)
{
    unsigned long long p=1;
    while(b)
    {
        if(b%2==0)
        {
        a=(a*a)%mod;
        b/=2;
        }
        else
        {
            p=(a*p)%mod;
            --b;
        }

    }
    return p%mod;
}

unsigned long long _combinari(unsigned long long a, unsigned long long b)
{
    unsigned long long numarator= f[a],numitor= f[b]*f[a-b]%mod;
    return numarator * _exp(numitor,mod-2)%mod;

}

int main()
{
        _read();
        _factorial();
        ofstream g("sandokan.out");
        g<<_combinari(n-1,(n-1)%(k-1));
        g.close();
    return 0;
}