#include<fstream>
using namespace std;

const int MOD = 1000003;

void read();
void comp();
void write();

int n, p;
bool ok[100001];
long long din[100001];

int main()
{
	read();
	comp();
	write();
}

void read()
{
	ifstream fin("grigo.in");
	fin >> n >> p;
	for (int i = 0, aux; i < p; ++i)
		fin >> aux, ok[aux] = true;
}

void write()
{
	ofstream fout("grigo.out");
	fout << din[n];
}

void comp()
{
	din[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		if (ok[i])
			din[i] = din[i - 1];
		else
			din[i] = (i - 1) * din[i - 1];
		din[i] %= MOD;
	}
		
}