#include <stdio.h>
#define MOD 1000003
#define N 100001
using namespace std;

int n,i,m,x;
int VIZ[N];
int A[N];

FILE *f, *g;

int main()
{
	f=fopen("grigo.in","r");
	g=fopen("grigo.out","w");
	
	fscanf(f,"%d %d",&n,&m);
	for (i=1;i<=m;++i)
	{
		fscanf(f,"%d",&x);
		VIZ[x]=1;
	}
	A[0]=1;
	for (i=1;i<=n;++i)
		if (VIZ[i]==1)
			A[i]=A[i-1];
		else
			A[i]=((long long)A[i-1]*(i-1))%MOD;
	fprintf(g,"%d",A[n]);
	fclose(f);
	fclose(g);
	return 0;
}