#include <stdio.h>
FILE *f=fopen("grigo.in","r"),*g=fopen("grigo.out","w");
int i,n,m,p[100001],x[100001],a;
int main(void)
{
	fscanf(f,"%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		fscanf(f,"%d",&a);
		x[a]=1;
	}
	for (i=1;i<=n;i++)
	if (x[i]) if (i!=1) p[i]=p[i-1]; else p[i]=1;
	else p[i]=((long long)p[i-1]*(i-1))%1000003;
	fprintf(g,"%d\n",p[n]);
	fclose(g);
	return 0;
}