#include <stdio.h>
#include <algorithm>
using namespace std;
#define N 5100
#define R 2000003
int v[N];
int n,m,k,rez=1;
void scan()
{
	freopen("sandokan.in", "r",stdin);
	freopen("sandokan.out", "w",stdout);
	scanf("%d%d", &n,&k);
	m=n;
	for(int i=1;i<=n;++i)
		scanf("%d", &v[i]);
	sort(v+1,v+n+1);
	//for(int i=2;i<=n;++i)
		//if(v[i]==v[i-1])
			//--m;	
}
void solve()
{
	long long aux;
	while(m)
	{
		aux=1;
		for(int i=1;i<=m;++i)
			aux*=i;
		for(int i=1;i<=m-k;++i)
			aux/=i;
		aux/=k;
		rez*=(aux%R);
		m-=k+1;
	}
	printf("%d\n", rez%R);
}
int main()
{
	scan();
	solve();
	return 0;
}