#include <stdio.h>
#define N 5100
#define R 2000003
int a[N],b[N],v[N];
int i,j,t,x,n,k,rez=1;
void scan()
{
	freopen("sandokan.in", "r",stdin);
	freopen("sandokan.out", "w",stdout);
	scanf("%d%d", &n,&k);
	for(i=1;i<=n;++i)
		scanf("%d", &v[i]);
}
void solve()
{
	a[0]=1;
    for (i=1;i<n;++i)
        for (j=1;j<=k;++j)
            b[j]=a[j-1]+a[j];
        for (j=1;j<=k;++j)
            a[j]=b[j]%R;
    x=n;
    while(x>=k)
	    x=x%k+x/k;
    rez=a[x-1];
	printf("%d\n", rez);
}
int main()
{
	scan();
	solve();
	return 0;
}