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