#include <cstdio>
#define IN "grigo.in"
#define OUT "grigo.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i) 
#define N_MAX 100001
#define MOD 1000003

int N,M;
int p[N_MAX];

void scan()
{
	int x;
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d%d",&N,&M);
	FOR(i,1,M)
	{
		scanf("%d", &x);
		p[x]=1;
	}	
}	

void solve()
{
	int rez=-1;
	if(M == 1)
		rez = 1;
	if( M == N || M == N-1)
		rez = 1;
	if(p[1] != 1)
		rez = 0;
	
	if(rez== -1)
	{
		rez = 1;
		FOR(i,1,N-1)
			rez = (rez*i)%MOD;
	}	
		
	//rez += MOD;	
	/*FOR(i,1,N)
	{
		if(!p[i])
		{
			sol -= 
			if(sol < MOD)
				sol += MOD;
			FOR(j,1,i-1)
			{
				sol -= 
				if(sol < MOD)
					sol += MOD;
			}
		}	
	}*/		
	printf("%d\n",rez%MOD);
}

int main()
{
	scan();
	solve();
	return 0;
}