#include<stdio.h>
int n,m;
long long v[100002];

void read()
{
	freopen("grigo.in","r",stdin);
	freopen("grigo.out","w",stdout);
	scanf("%d%d",&n,&m);
	int ind,i;
	for(i=1;i<=n;i++)
		scanf("%d",&ind),v[ind]=1;
	v[0]=1;
	for(i=1;i<=n;i++)
	{
		if(!v[i])
			v[i]=(v[i-1]*(i-1))%1000003;
		else
			v[i]=v[i-1];
	}
	printf("%lld\n",v[n]);
}

int main()
{
	read();
	return 0;
}