#include <stdio.h>
#include <algorithm>
#define NMAX 100005
#define ll long long
#define MOD 1000003
using namespace std;
int n,m,A[NMAX],D[NMAX];
char marc[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i;
	for (i=1; i<=m; i++)
		scanf("%d",&A[i]);
	sort(A+1,A+m+1);
	for (i=1; i<=m; i++)
		marc[A[i]]=1;
}
void solve()
{
	D[1]=1;
	int i;
	for (i=2; i<=n; i++)
		if (marc[i])
			D[i]=D[i-1];
		else
			D[i]=((ll)D[i-1]*(i-1))%MOD;
}
int main()
{
	freopen("grigo.in","r",stdin);
	freopen("grigo.out","w",stdout);
	read();
	solve();
	printf("%d\n",D[n]);
	return 0;
}