#include <stdio.h>
#define NMAX 100001
#define MOD 1000003

long n, m, T0, T1, x[NMAX];

int main() {
	FILE *f = fopen("grigo.in", "r");
	FILE *g = fopen("grigo.out", "w");
	fscanf(f, "%ld %ld", &n, &m);
	long i, j;
	for(i = 1; i <= m; i++){
		fscanf(f, "%ld", &j);
		x[j]=1;
	}
	T1 = 1;
	for(i = 1; i <= n; i++){	
		if(x[i]) T0 = T1 ; 
		    else T0 = ((long long)(i-1) * T1) % MOD;
		T1 = T0;
	}	
	fprintf(g, "%ld\n", T0);
	fclose(f);
	fclose(g);
	return 0;
}