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