#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("grigo.in");
ofstream out("grigo.out");
const int N = 100005;
const int MOD = 1000003;
long long factorial(int x){
	long long p=1;
	for(int i=1;i<=x;i++){
		p*=i;
		p%=MOD;
	}
	return p;
}
int n,m,v[N];
int main(){
	in>>n>>m;
	for(int i=1;i<=m;i++) in>>v[i];
	sort(&v[1],&v[m+1]);
	if(v[1]==1) out<<factorial(n-m+1);
	else out<<0;
	return 0;
}