#include<stdio.h>
#define N 2000003
int c[2][5000];
int main () {
	freopen("sandokan.in","r",stdin);
	freopen("sandokan.out","w",stdout);
	int n,k,i,cn,v[5000],j,x;
	scanf("%d%d",&n,&k);
	for(i=0;i<n;++i)
		scanf("%d",&v[i]);
	cn=n;
	while(cn>=k)
		cn=cn-k+1;
	k=cn;
	--n;--k;
	c[0][0]=c[0][1]=1;
	for(i=2;i<=n;++i){
		c[1][0]=1;
		for(j=1;j<=i;++j)
			c[1][j]=(c[0][j-1]+c[0][j])%N;
		for(x=0;x<j;++x)
			c[0][x]=c[1][x];
	}
	printf("%d\n",c[1][k]%N);
	return 0;
}