#include<stdio.h>
#define NMAX 100001

long i, j, n, m, x, ok[NMAX];
long long a[NMAX];
FILE *fin, *fout;

int main()
{
	fin = fopen("grigo.in", "rt");
	fout = fopen("grigo.out", "wt");

	fscanf(fin, "%ld %ld", &n, &m);

	for(i = 1; i <= m; i++)
	{
		fscanf(fin, "%ld", &x);

		ok[x] = 1;
	}

	a[1] = 1;
	for(i = 2; i <= n; i++)
	{
		a[i] = a[i - 1];

		if(ok[i] == 0)
			a[i] = (a[i] * (i - 1)) % 1000003;
	}

	fprintf(fout, "%ld\n", a[n]);


	return 0;
}