#include <stdio.h>
#define N 2000001
#define R 2000003
bool v[N];
int n,m,k,rez=1;
void scan()
{
	int e;
	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", &e);
		if(v[e])
			--m;
		v[e]=1;
	}
}
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;
}