#include <stdio.h>

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

int main(){
    freopen("sandokan.in","r",stdin);
    freopen("sandokan.out","w",stdout);
    scanf("%ld %ld",&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;
            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;
    }
    printf("%lld\n",r);

return 0;
}