#include <fstream>
#define RUN_EXE int main(){exe();return 0;}
#include <vector>

using namespace std;
const int MOD=1000003;
const int NMax=1<<20;

ifstream in("grigo.in");
ofstream out("grigo.out");

int N,M,rez=1;
vector <bool> B(NMax);

void read(){
	in>>N>>M;
}

void to_M(){
	for(int i=1,x;i<=M;++i){
		in>>x;
		B[x]=true;
	}
}

void proB(){
	for(int i=2;i<=N;++i){
		if(!B[i]){
			rez=((long long)rez*(i-1))%MOD;
		}
	}
}

void afis(){
	out<<rez;
}

void exe(){
	read();
	to_M();
	proB();
	afis();
}

RUN_EXE