#include<stdio.h>
#include<algorithm>
#define modulo 1000003
#define N_MAX 100005
using namespace std;
int a[N_MAX],d[N_MAX],n,m;
long long aux;
int main()
{ int i, j;
	freopen("grigo.in", "r", stdin);
	freopen("grigo.out", "w", stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+m+1);
	j=1;
	d[0]=1;
	for(i=1;i<=n;i++)
	{
		d[i]=d[i-1];
		if(i==a[j]) j++;
			else 
			{
				aux=((long long)d[i-1]*(long long)(i-1))%(long long)modulo;
				d[i]=aux;
			}
	}
	printf("%d\n",d[n]);
	return 0;
}