#include <stdio.h>
#include <string.h>
#define MOD 2000003
#define NMAX 5001
int n,k,v[NMAX],ind,ind2;
int comb[2][NMAX];
void precompute()
{
	ind=1;
	comb[ind][0]=1;
	comb[ind][1]=1;
	int i,j;
	for (i=2; i<=n-1; i++)
	{
		ind=(i-1) & 1;
		ind2=i & 1;
		for (j=1; j<=n; j++)
			comb[ind2][j]=0;
		comb[ind2][0]=1;
		for (j=1; j<=i; j++)
		{
			comb[ind2][j]=comb[ind][j]+comb[ind][j-1];
			if (comb[ind2][j]>=MOD)
				comb[ind2][j]-=MOD;
		}
	}
}
int main()
{
	freopen("sandokan.in","r",stdin);
	freopen("sandokan.out","w",stdout);
	scanf("%d%d",&n,&k);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d",&v[i]);
	int p = n % ( k - 1 ) ;
	if ( p == 0 ) p = k - 1;
	precompute();
	printf("%d\n",comb[ind2][p-1]);
	return 0;
}