#include <cstdio>

#define file_in "grigo.in"
#define file_out "grigo.out"

int n,m,x;
int v[101000];

void citire(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);

	scanf("%d %d", &n, &m);
	for (int i=1;i<=m;++i)
		 scanf("%d", &x),
		 v[x]=1;
}

#define mod 1000003

void solve(){
	
	int p=1;
	for (int i=1;i<=n;++i)
		 if (!v[i])
			  p=(1LL*p*(i-1))%mod;
	printf("%d\n", p);
}

int main(){
	
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}