#include <stdio.h>
#define R 2000003
int b[5000],a[5000];
int  n,k,i,j,t,x;
int main()
{
    freopen("sandokan.in", "r",stdin);
    freopen("sandokan.out", "w",stdout);
    scanf("%d%d",&n,&k);
    a[0]=1; x=n;
    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;
    }
    while(x>=k) x=x%k+x/k;
    k=1;
    printf("%d\n", a[x-1]);
    return 0;
}