#include<stdio.h>
#define mod 2000003
#define baza 10000
int a[50000],t,i,r,n,j,k,p;

int main()
{
	freopen("sandokan.in","r",stdin);
	freopen("sandokan.out","w",stdout);
	
	scanf("%d %d",&n,&k);
	
	r=(n-1)%(k-1);
	
	if(!r) {printf("1"); return 0;}
	else if(r==1) {printf("%d",n-1); return 0;}
	
	
	p=n-r;
	k=0;
	while(p)
	{
		a[++k]=p%baza;
		p/=baza;
	}
	
	p=n-r+1;
	
	for(j=p;j<n;j++)
	{
		for(t=0,i=1;i<=k||t;i++,t/=baza)
			a[i]=(t+=a[i]*j)%baza;
		k=i-1;
	}
	
	for(j=1;j<=r;j++)
	{
		for(t=0,i=k;i;i--,t%=j)
			a[i]=(t=t*baza+a[i])/j;
		
		for(;k>1 && !a[k];k--);
	}
	
	for(r=0,i=k;i;i--)
		r=(r*baza+a[i])%mod;
	
	printf("%d",r);
	
	return 0;
}