#include <fstream>
using namespace std;

const char FILEIN[] = "grigo.in";			// input file
const char FILEOUT[] = "grigo.out";			// output file
const int MAX_N = 100005;					// maximum number of elements
const int MOD = 1000003;					// the result must be printed modulo MOD

int N;						// number of elements
int M;						// number of visible elements
bool visible[MAX_N];		// visible[i] = true iff i must be visible
long long nrp[MAX_N];		// nrp[i] = number of permutations of length i

void ReadData() {
	ifstream fin(FILEIN);

	fin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int elem;
		fin >> elem;
		visible[elem] = true;
	}
}

void Solve() {
	nrp[0] = 1;
	for (int i = 1; i <= N; ++i)
		nrp[i] = (visible[i] ? nrp[i-1] : nrp[i-1] * (i-1)) % MOD;
}

void WriteData() {
	ofstream fout(FILEOUT);

	fout << nrp[N];
}

int main() {
	ReadData();
	Solve();
	WriteData();
}

/*
Adventure seeker on an empty street
Just an alley creeper light on his feet
A young fighter screaming with no time for doubt
With the pain and anger cant see a way out
It aint much Im asking I heard him say
Gotta find me a future move out of my way
I want it all I want it all I want it all and I want it now
I want it all I want it all I want it all and I want it now

Listen all you people come gather round
I gotta get me a game plan gotta shake you to the ground
Just give me what I know is mine
People do you hear me just give me the sign
It aint much Im asking if you want the truth
Heres to the future for the dreams of youth
I want it all (give it all) I want it all I want it all and I want
It now
I want it all (yes I want it all) I want it all (hey)
I want it all and I want it now

Im a man with a one track mind
So much to do in one life time (people do you hear me)
Not a man for compromise and wheres and whys and living
Lies
So Im living it all (yes Im living it all)
And Im giving it all (and Im giving it all)

Yeah yeah
Yeah yeah yeah yeah
I want it all all all all

It aint much Im asking if you want the truth
Heres to the future
Hear the cry of youth (hear the cry hear the cry of youth)
I want it all I want it all I want it all and I want it now
I want it all (yeah yeah yeah) I want it all I want it all and i
Want it now

I want it
Now
I want it I want it
*/