#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 100010
#define mod 1000003

int n, m;
int a[maxn];
int v1, v2,i,j;

int main()
{
	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);
	v1=1;
	j=1;
	for(i=1;i<=n;i++) 
	{
		v2=v1;
		if(a[j]==i) 
		{
			v1=v2;
			j++;
		}
		else v1=(1LL*(i-1)*v2)%mod;
	}
	printf("%d\n", v1);
	return 0;
}