#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 1 << 17;
const int MOD = 1000003;
int N, M, R, A[NMAX];
void read(void) {
	ifstream fin("grigo.in");
	int i;
	fin >> N >> M;
    for (i = 0; i < M; ++i)
		fin >> A[i];
	sort(A, A + M);
	fin.close();}
void solve(void) {
	int i, j, v;
	A[M] = N + 1; R = 1;
	for (i = M - 1; i >= 0; --i) {
		for (v = A[i+1] - 2, j = A[i + 1] - A[i]; j > 1; --j, --v)
			R = ((long long) R * v) % MOD;	}}
void write(void) {
	ofstream fout("grigo.out");
	if (A[0] != 1) R = 0;
	fout << R << '\n';
    fout.close();
}
int main(void) {
	read();
	solve();
	write();
	return 0;
}