#include<stdio.h>
#include<fstream>
using namespace std;

ifstream f("grigo.in");
ofstream g("grigo.out");

#define MaxN 100100
#define Mod 1000003

int N,M,MAX = 1,A[MaxN];

int main()
{
	f >> N >> M;
	for(int i=1;i<=M;i++)
	{
		f >> A[0];
		A[A[0]] = 1;
	}
	
	for(int i=2;i<=N;i++)
		if(!A[i])
			MAX = 1LL*MAX*(i-1)%Mod;
		
	g << MAX;
	
	return 0;
}