#include <cstdio>
#define IN "grigo.in"
#define OUT "grigo.out"
#define MOD 1000003
#define N_MAX 100001
#define FOR(i,a,b) for(int i=a;i<=b;++i)

int N,K;
int poz[N_MAX],sol[N_MAX];

int main()
{
	int x;
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d%d\n", &N,&K);
	FOR(i,1,K)
		scanf("%d", &x),
		poz[x] = 1;
	
	sol[1] = 1;	
	FOR(i,2,N)
		if(poz[i])
			sol[i] = sol[i-1];
		else
			sol[i] = ((long long) sol[i-1] * (i-1)) % MOD; 
	printf("%d\n",sol[N]);
	return 0;
}