#include<stdio.h>
long long n,k,r,u,d,sol;
int main()
{
	FILE *f=fopen("sandokan.in","r"),
	     *g=fopen("sandokan.out","w");
	fscanf(f,"%lld%lld",&n,&k);
	r=n%(k-1);
        r=r?r:(k-1);
	if(r==1){fprintf(g,"1\n");fcloseall();return 0;}
	u=n-1;d=1;sol=1;
	for(i=1;i<r;i++)
	{ sol*=u;sol/=d;u--;d++;}
	sol%=2000003;
	fprintf(g,"%lld\n",sol);
        fcloseall();
	return 0;
}