#include <stdio.h>

long n, i, j, m, poz, sol[100001];
char v[100001];

int main()
{
	freopen ("grigo.in", "rt", stdin);
	freopen ("grigo.out", "wt", stdout);

	scanf("%ld %ld", &n, &m);
	for (i = 1; i <= m; ++i)
		scanf("%ld", &poz), v[poz] = 1;

	sol[1] = 1;
	for (i = 2; i <= n; ++i)
	{
		if (v[i])
			sol[i] = sol[i - 1];
		else
			sol[i] = (((i - 1) % 1000003) * sol[i - 1]) % 1000003;
	}

	printf("%ld\n", sol[n]);

	return 0;
}