#include<stdio.h>
#include<algorithm>
using namespace std;
#define modulo 1000003
#define NMAX 100005

int A[NMAX], C[NMAX], N, M;

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;
	C[0] = 1;
	
	for(i = 1; i <= N; i++)
	{
		C[i] = C[i-1];
		
		if(i == A[j]) j++;
			else C[i] = (C[i]*(i-1))%modulo;
	}
	
	printf("%d\n", C[N]);
	
	return 0;
}