#include <iostream>
#include <fstream>

using namespace std;

const char iname[] = "grigo.in";
const char oname[] = "grigo.out";
const int  nmax    = 100005;
const int  mod     = 1000003;

ifstream fin(iname);
ofstream fout(oname);

int n, k, vis[nmax], i, p[nmax], x, ct, last, first, sol, ls;
int perm[nmax], cateam;
	

int main()
{
	fin >> n >> k;
	for(i = 1; i <= k; i ++)
	{	
		fin >> x;
		vis[x] = 1;
		last = x;
	}
	
	/*perm[0] = 1;
	for(i = 1; i <= 100005; i ++)
		perm[i] = (long long)(perm[i - 1] * i) % 1000003;
*/

		
	p[0] = 1;
	for(i = 1; i <= n; i ++)
	{
		if(vis[i] == 1)
			p[i] = p[i - 1];
		else
			p[i] = (long long)(p[i - 1] * (i - 1)) % mod;
	}

/*	
	if(first == 1)
	{
		ls = 1;
		sol = n - k + 1;
	}
		
	for(i = 1; i <= n; i ++)
	{
		if(i == first)
		{
			sol = n - k + 1;
			ls = i;
		}
		if(i != first && vis[i] == 1)
		{
			sol = sol * perm[i - ls];
			ls = i;
		}
		if(i == last)
			sol = sol * perm[n - last];
	}
	
	*/		
	
	//fout << sol;
	fout << p[n];
	return 0;
}