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

void read()
{
	freopen("grigo.in","r",stdin);
	freopen("grigo.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	long ind,i;
	for(i=1;i<=m;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;
}