#include<stdio.h>
long long n,k,r,u,i,d,sol,m,uu,dd,p,a[50],b[50],x[50],y[50];
int main()
{
    FILE *f=fopen("sandokan.in","r"),
	 *g=fopen("sandokan.out","w");
    fscanf(f,"%lld%lld",&n,&k);m=2000003;
    r=n%(k-1);
    if(r==1){fprintf(g,"1\n");fcloseall();return 0;}
    u=n-1;d=1;sol=1;uu=1;dd=1;
    for(i=1;i<r;i++)
    { uu=(uu*u)%m;dd=(dd*d)%m;u--;d++;}
    a[0]=dd;b[0]=m;p=0;
    while(a[p])
    { p++;a[p]=b[p-1]%a[p-1];b[p]=a[p-1];}
    y[p]=1;
    while(p)
    {  x[p-1]=y[p]-(b[p-1]/a[p-1])*x[p];y[p-1]=x[p];p--;}
    dd=x[0];
    while(dd<0) dd+=m;
    while(dd>=m)dd-=m;
    sol=(uu*dd)%m;
    fprintf(g,"%lld\n",sol);
    fcloseall();
    return 0;
}