#include <cstdio>
using namespace std;

bool viz[100000]={0};
int n,m,i,arg;
long long sol=1;
int main () {
	
	freopen ("grigo.in", "r", stdin);
	freopen ("grigo.out", "w", stdout);
	
	
	scanf ("%d %d", &n, &m);
	
	for (i=1; i<=m; i++){
		scanf ("%d", &arg);
		viz	[arg]=1;
	}
	
	for (i=1; i<=n; i++) {
		if (viz[i]==0) sol=(sol*(long long)(i-1))%1000003;
	}
	
	printf ("%lld", sol%1000003);
	
	return 0;
}