#include <cstdio>
#define ll long long
#define N 5003
#define M 2000003

int n,k;
int prod[N];

inline ll invMod(ll x)
{
	ll r=1;
	int aux=M-2;
	for(; aux; aux>>=1)
	{
		if(aux&1)
			r=(r*x)%M;
		x=(x*x)%M;
	}
	return r;
}

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

	scanf("%d%d",&n,&k);
	if(k==2)
	{
		printf("1\n");
		return 0;
	}

	k=(n-1)%(k-1);
	prod[0]=prod[1]=1;
	for(int i=2; i<=n; ++i)
		prod[i]=((ll)prod[i-1]*(ll)i)%M;
	
	printf("%lld\n",((((ll)prod[n-1]*invMod(prod[k]))%M)*invMod(prod[n-k-1]))%M);
	return 0;
}