#include <cstdio>

const int N = 5001;
const int MOD = 2000003;

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

int main() {
	freopen("sandokan.in","rt",stdin);
	freopen("sandokan.out","wt",stdout);
	scanf("%d %d",&n,&k);
	for (p = n; p >= k; p -= k-1);
	c[0][0] = 1;
	for (int i = 1; i < n; ++i) {
		c[i&1][0] = 1;
		c[i&1][i] = 1;
		for (int j = 1; j < i; ++j)
			c[i&1][j] = (c[!(i&1)][j-1] + c[!(i&1)][j]) % MOD;
	}
	printf("%d\n",c[(n-1)&1][p-1]);
	return 0;
}