#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 100010
#define mod 1000003

int n, m;
int a[maxn];
int v1, v2;

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

	scanf("%d %d ", &n, &m);

	int i, j;

	for (i=1; i<=m; i++) scanf("%d ", &a[i]);

	sort(a+1, a+m+1);

	v1 = 1;
	j = 1;

	for (i=1; i<=n; i++) 
	{
		v2 = v1;
		if (a[j] == i) 
		{
			v1 = v2;
			j++;
		}
		else v1 = (1LL * (i-1) * v2) % mod;
	}

	printf("%d\n", v1);
	return 0;
}