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