#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#define NMAX 5005
#define MOD 2000003
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

typedef pair<int, int> pii;

ifstream fin("sandokan.in");
ofstream fout("sandokan.out");

int comb[2][NMAX];

int main() {
	int n,k,i,j,ramase,ind;

	fin>>n>>k;

	ramase=n%(k-1);
	if(!ramase) ramase=k-1;

	comb[0][0]=1;
	for(i=1;i<=n-1;++i) {
		ind=i&1;
		comb[ind][0]=1;
		for(j=1;j<=ramase-1;++j)
			comb[ind][j]=(comb[ind^1][j-1]+comb[ind^1][j])%MOD;
	}

	fout<<comb[(n-1)&1][ramase-1];

	return 0;
}