#include <fstream>
using namespace std;
ifstream in("sandokan.in");
ofstream out("sandokan.out");
const int MOD=2000003;
int n,k;
int puterelogaritmica(int baza,int exponent)
{
    int rezultat=1;
    while(exponent>0)
    {
        if(exponent & 1)
           rezultat=1LL*rezultat*baza%MOD;
        baza=1LL*baza*baza%MOD;
        exponent/=2;
    }
    return rezultat;
}
int inversmodular(int valoare)
{
    return puterelogaritmica(valoare,MOD-2);
}
int combinari(int n,int k)
{
     if (k>n-k)
        k=n-k;
    int numarator=1,numitor=1;
    for (int i=1;i<=k;i++)
    {
        numarator=1LL*numarator*(n-i+1)%MOD;
        numitor=1LL*numitor*i%MOD;
    }
    numarator=1LL*numarator*inversmodular(numitor)%MOD;
    return numarator;
}
int main()
{
    in>>n>>k;
    int p=(n-1)%(k-1)+1;
    out<<combinari(n-1,p-1);
    in.close();
    out.close();
    return 0;
}