#include <stdio.h>

FILE *f,*s;

int n,m,i,k;
long long v[100005];

int main()
{
	f=fopen("grigo.in","r");
	s=fopen("grigo.out","w");
	
	fscanf(f,"%d %d\n",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%d ",&k);
		
		v[k]=1;
	}	
	
	v[0]=1;
	for(i=1;i<=n;i++)
	{
		if(v[i]==1)
			v[i]=v[i-1];
		else
			v[i]=((i-1)*v[i-1])%1000003;
	}	
	
	fprintf(s,"%lld",v[n]);
	
	fclose(s);
	
	return 0;
}