#include <cstdio>
#include <algorithm>

using namespace std;

#define MOD 1000003
#define maxN 100005

int p[maxN];

int main()
{
	freopen ("grigo.in", "r", stdin);
	freopen ("grigo.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N, &M);
	
	p[1] = 1;
	for (int i = 1; i <= M; ++ i)
	{
		int c;
		
		scanf ("%d", &c);
		
		p[c] = 1;
	}
	
	for (int i = 2; i <= N; ++ i)
		if (p[i]) p[i] = p[i - 1];
		else p[i] = (1LL * p[i - 1] * (i - 1)) % MOD;
	
	printf ("%d", p[N]);
	
	return 0;
}