#include <fstream>
#include <iostream>
#include <iterator>
#include <set>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
	int N, M, aux;

	ifstream fin("grigo.in");
	fin >> N >> M;
	set<int> F;
	for (int i = 0; i < M; ++i) {
		fin >> aux;
		F.insert(aux);
	}
	fin.close();

	vector<long long> sol(N+1, 0);
	sol[0] = 1;
	for (int i = 1; i <= N; ++i)
		if (F.find(i) == F.end())
			sol[i] = (long long)(i-1) * sol[i-1] % 1000003;
		else
			sol[i] = sol[i-1];

	ofstream fout("grigo.out");
	fout << sol[N] << endl;
	fout.close();

	return 0;
}