#include<stdio.h>

#define maxdim 100005
#define mod 1000003

FILE*f=fopen("grigo.in","r");
FILE*g=fopen("grigo.out","w");

int n,k;
int viz[maxdim];

int main () {
	
	fscanf(f,"%d %d",&n,&k);
	int x;
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d",&x);
		viz[x] = 1;
	}
	
	int sol = 1;
	if ( !viz[1] )	sol = 0;
	for ( int i = 2 ; i <= n ; ++i ){
		if ( !viz[i] ){
			sol = (1LL*sol*(i-1)) % mod;
		}
	}
	
	fprintf(g,"%d\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}