#include <stdio.h>

int n,k,i,j,a[2][5003],p;

int main()
{
	freopen("sandokan.in","r",stdin);
	freopen("sandokan.out","w",stdout);
	scanf("%d%d",&n,&k);
	k=(n-1)%(k-1);--n;
	a[0][0]=1; a[1][0]=1; p=0;
	for (i=1; i<=n; ++i)
	{
		p=1-p;
		for (j=1; j<=k; ++j)
		{
			if (j==i) { a[p][j]=1; break; }
			a[p][j]=(a[1-p][j-1]+a[1-p][j])%2000003;
		}
	}
	printf("%d\n",a[p][k]);
	return 0;
}