#include <iostream>
#include <fstream>

using namespace std;

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

const int MAXN = 100010;
const int MOD = 1000003;

long long Sol[MAXN];
bool visible[MAXN];

int main ()
{
	int N, M, x, i;
	
	in >> N >> M;
	
	for (i = 1; i <= M; i ++)
		in >> x, visible[x] = 1;
	
	Sol[0] = 1;
	for (i = 1; i <= N; i ++)
		if (visible[i])
			Sol[i] = (1LL * Sol[i - 1]) % MOD;
		else
			Sol[i] = (1LL * (long long) (i - 1) * Sol[i - 1]) % MOD;
		
	out << (Sol[N] % MOD);
	
	return 0;
}