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

long n, m, T0[NMAX], 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, nr=0;
	for(i = 1; i <= m; i++){
		fscanf(f, "%ld", &j);
		x[j]=1;
	}
	T0[0] = 1;
	for(i = 1; i <= n; i++)
			{
				if(x[i]) { T0[i] = (long long)T0[i - 1] ; nr++; }
				else T0[i] = (long long)(i-nr+1) * T0[i - 1];
				T0[i] %= MOD;
			}
	fprintf(g, "%ld\n", T0[n]);
	fclose(f);
	fclose(g);
	return 0;
}