#include <fstream>
#include <algorithm>
#define MOD 1000003LL
using namespace std;
ifstream fi("grigo.in");
ofstream fo("grigo.out");
int N,M,i,poz,k,j;
int n;
int P[100001];
int F[100001];
long long rez;

int prim(int n)
// determina cel mai mic divizor al lui n
{
	int d;
	if (n<=1)
		return 1;
	if (n%2==0)
		return 2;
	for (d=3;d*d<=n;d=d+2)
		if (n%d==0)
			return d;
	return n;
}

void desc(int x)
// conduce la cresteri de valori in sirul F
{
	int d;
	while (x>1)
	{
		d=prim(x);
		while (x%d==0)
		{
			F[d]++;
			x=x/d;
		}
	}
}



int main()
{
	fi>>N>>M;
	for (i=1;i<=M;i++)
		fi>>P[i];
	sort(P+1,P+M+1);
	if (P[1]!=1)
	{
		fo<<0;
		fi.close();
		fo.close();
		return 0;
	}
	poz=N;
	for (i=M;i>=1;i--)
	{
		// la rezultat se socoteste A[ind-1,ind-P[i]]
		n=poz-1;
		k=poz-P[i];
		for (j=n-k+1;j<=n;j++)
			desc(j);
		poz=P[i]-1;
	}
	rez=1LL;
	for (i=2;i<=100000;i++)
		for (j=1;j<=F[i];j++)
			rez=(rez*(long long)i)%MOD;
	fo<<rez;
	return 0;
}