#include<stdio.h>
#define infile "grigo.in"
#define outfile "grigo.out"
#define mmax 100*1000+1
#define modulo 1000*1000+3
char v[mmax]; //vectorul in care marcam cu 1 pozitiile ce trebuie sa fie vizibile
int n;

void citire(char v[mmax], int *n)
	{
	int m,x;
	scanf("%d %d\n",n,&m); //citim numarul de elemente ale permutarii, si numarul de pozitii vizibile
	while(m--) //citim toate pozitiile ce trebuie facute vizibile
		{
		scanf("%d",&x); //citim pozitia ce trebuie sa fie vizibila
		v[x]=1; //marcam ca trebuie sa fie vizibila
		}
	}

int calc_permutari(char v[mmax], int n)
	{
	int s=1; //variabila in care calculam numarul de permutari
	int i;
	for(i=2;i<=n;i++) //fiecare element al permutarii
		if(!v[i]) //daca este o pozitie ce nu trebuie sa fie vizibila
			s*=(i-1)%modulo; //
	return s;
	}

int main()
{
//deschidem fisiere
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(v,&n); //citim
printf("%d",calc_permutari(v,n)); //calculam si afisem numarul de permutari

//inchidem fisiere
fclose(stdin);
fclose(stdout);
return 0;
}