#include <cstdio>

#define MAXN 100005
#define PRIM 1000003

int N, M;
int ind[MAXN];
long long d[MAXN];

int main () {
	freopen ("grigo.in", "r", stdin);
	freopen ("grigo.out", "w", stdout);

	int p;
	for (scanf ("%d %d", &N, &M); M; -- M) {
		scanf (" %d", &p);
		ind[p] = 1;
	}

	d[1] = 1;
	for (int i = 2; i <= N; ++ i)
		if (ind[i]) d[i] = d[i-1];
		else d[i] = ((i-1) * d[i-1]) % PRIM;

	printf ("%lld\n", d[N]);

	return 0;
}