#include <fstream>

using namespace std;

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

long n,m,k,i,j,q,rez[100005],baza=100005;
long long r,modulo=2000003;

int main(){

    fin>>n>>k;

    m=n%(k-1);
    if (!m)m=k-1;

    q=1;
    rez[1]=1;
    for (i=1;i<m;i++){
        r=0;
        for (j=1;j<=q;j++){
            rez[j]=rez[j]*(n-i)+r;
            r=rez[j]/baza;
            rez[j]%=baza;
        }
        while (r){
            q++;
            rez[q]=r%baza;
            r/=baza;
        }
        for (j=q;j;j--){
            rez[j-1]+=(rez[j]%i)*baza;
            rez[j]/=i;
        }
        while (!rez[q])q--;

    }
    r=0;
    for (i=q;i;i--){
        r=(long long)r*baza;
        r+=rez[i];
        r=(long long)r%modulo;
    }
    fout<<r;
return 0;
}