//Ilie Dumitru
#include<cstdio>
const int NMAX=100005;
const int MOD=1000003;

int N, M;
int v[NMAX];

int main()
{
	FILE* f=fopen("grigo.in", "r"), *g=fopen("grigo.out", "w");
//	FILE* f=stdin, *g=stdout;
	int i, j, ans=1;

	fscanf(f, "%d%d", &N, &M);
	for(i=0;i<M;++i)
		fscanf(f, "%d", v+i);

	if(v[0]!=1)
		ans=0;

	for(i=1, j=0;i<=N;++i)
	{
		if(j<M && v[j]==i)
			++j;
		else
			ans=ans*(long long int)(i-1)%MOD;
	}

	fprintf(g, "%d\n", ans);

	fclose(f);
	fclose(g);
	return 0;
}