#include <cstdio>
#define DIM 8192
#define MOD 1000003

int dp[100001];
int n,M;
bool use[100001];

char ax[DIM];
int pz;

inline void cit(int &x)
{
	x=0;
	while(ax[pz]<'0' || ax[pz]>'9')
		if(++pz==DIM)fread(ax, 1, DIM, stdin),pz=0;
	
	while(ax[pz]>='0' && ax[pz]<='9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
	}
}

void solve()
{
	if(use[1]==0) { printf("0\n");return;}
	dp[1]=1;
	int i;
	for(i=2;i<=n;++i)
		if(use[i]) dp[i]=dp[i-1];
		else dp[i]=dp[i-1]*(i-1), dp[i]%=MOD;
	
	printf("%d\n", dp[n]);
}
	

int main()
{
	freopen("grigo.in","r",stdin);
	freopen("grigo.out","w",stdout);
	cit(n);cit(M);
	int p,i;
	for(i=1;i<=M;++i)
	{
		cit(p);
		use[p]=1;
	}
	
	solve();
	return 0;
}