#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;
}