#include <stdio.h>
#include <algorithm>
#define mx 100010
#define r_rez 1000003

using namespace std;

int n, k, x;
int v[mx];

int main()
{
	freopen("grigo.in","r",stdin);
	freopen("grigo.out","w",stdout);
	scanf("%ld %ld", &n, &k);
	for (int i = 0; i < k; i++)
	{
		scanf("%ld", &x);
		v[x] = 1;
	}
	long long s = 1;
	for (int i = 1; i <= n; i++)
		if (!v[i])
			s = (long long) (s * (i - 1)) % r_rez;
	printf("%lld\n", s);
	fclose(stdin);
	fclose(stdout);
	return 0;
}