#include <stdio.h>

#define MOD 2000003
#define DIM 5005

int c[2][DIM];
int n,k,p;

void solve ()
{
    int i,j,l;

    for (p=n; p>=k; p-=k-1);
    c[0][0]=c[1][0]=1;
    for (l=i=1; i<n; ++i, l^=1)
	for (j=1; j<=i; ++j)
	    c[l][j]=(c[l^1][j-1]+c[l^1][j])%MOD;
    printf ("%d",c[l^1][p-1]);
}

int main ()
{
    freopen ("sandokan.in","r",stdin);
    freopen ("sandokan.out","w",stdout);

    scanf ("%d%d",&n,&k);
    solve ();

    return 0;
}