#include<stdio.h>
#define lg 1000003
long long v[100000];
long long n,m,x,i;
int main () {
	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]=v[i-1];
		else
			v[i]=(((i-1)%lg)*v[i-1])%lg;
	printf("%lld",v[n]);
	return 0;
}