#include <stdio.h>
#define MOD 2000003
using namespace std;

int n,i,k;
int A[5001];
int X[5001];

FILE *f,*g;

int myfct(int n, int k)
{
	int i,j;
	X[0]=1;
	if (n<k)
		return 1;
	for (i=1;i<=n;++i)
		for (j=i;j>=1;--j)
			X[j]=(X[j-1]+X[j])%MOD;
	return X[k];
}

int main()
{
	f=fopen("sandokan.in","r");
	g=fopen("sandokan.out","w");
	
	fscanf(f,"%d %d",&n,&k);
	for (i=1;i<=n;++i)
		fscanf(f,"%d",&A[i]);
	fprintf(g,"%d",myfct(n-1,(n-1)%(k-1)));
	fclose(f);
	fclose(g);
	return 0;
}