#include<fstream>
using namespace std;
int n, k, i, x, j, r;
int c[5002];
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int main(){
	fin>> n >> k;
	for(i = 1; i <= n; i++){
		fin>> x;
	}
	r = n % (k - 1);
	if(r == 0){
		r = k - 1;
	}
	r--;
	c[0] = 1;
	for(i = 1; i <= n; i++){
		for(j = i; j > 0; j--){
			c[j] += c[j-1];
			c[j] %= 2000003;
		}
	}
	fout<< c[r];
	return 0;
}