#include <iostream>
#include <fstream>

using namespace std;

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

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

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

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;


		
	
	for(i = 1; i <= n; i ++)
	{
		if(vis[i] == 1)
			{
				first = i;
				break;
			}
	}
	
	if(first == 1)
	{
		ls = 1;
		sol = 1;
	}
		
	for(i = 1; i <= n; i ++)
	{
		if(i == first  && first != 1)
		{
			sol = perm[first - 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;
	return 0;
}