#include<stdio.h>
#define mod 2000003
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;
	
	while(p)
	{
		a[++a[0]]=p%10;
		p/=10;
	}
	
	p=n-r+1;
	
	for(j=p;j<n;j++)
	{
		for(t=0,i=1;i<=a[0]||t;i++,t/=10)
			a[i]=(t+=a[i]*j)%10;
		a[0]=i-1;
	}
	
	for(j=1;j<=r;j++)
	{
		for(t=0,i=a[0];i;i--,t%=j)
			a[i]=(t=t*10+a[i])/j;
		
		for(;a[0]>1 && !a[a[0]];a[0]--);
	}
	
	for(r=0,i=a[0];i;i--)
		r=(r*10+a[i])%mod;
	
	printf("%d",r);
	
	return 0;
}