#include <fstream>
#define mod 2000003
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int n,k,r,i,j,C[5010],x;
int main() {
	fin>>n>>k;
	for (i=1;i<=n;i++)
		fin>>x;
	n--; k--; r=n%k;
	C[1]=1;
	for (i=2;i<=n+1;i++)
		for (j=i;j>=1;j--)
			C[j]=(C[j-1]+C[j])%mod;
	fout<<C[r+1];
	return 0;
}
/**
mereu se 'sterg' k-1 elemente din n-1(maximul ramane mereu)
deci avem C(n-1,k-1)
**/