#include<stdio.h>  
#define MOD 1000003
int v[100001];
int main(){
	int x,m,n,i;
	freopen("grigo.in","r",stdin);
	freopen("grigo.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i){
		scanf("%d",&x);
		v[x]=1;
	}
	for(i=2;i<=n;++i)
		if(!v[i])
			v[i]=(((i-1)%MOD)*v[i-1])%MOD;
		else
			v[i]=v[i-1];
	printf("%d\n",v[n]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}