#include<stdio.h>  
#define MOD 1000003
long long v[100001];
int main(){
	long long x,m,n,i;
	freopen("grigo.in","r",stdin);
	freopen("grigo.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=m;++i){
		scanf("%lld",&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("%lld\n",v[n]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}