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

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