#include <cstdio>

const int MOD = 1000003 ;
const int MAX_N = 100001 ;

bool vizibil[MAX_N] ;
int n,k,x ;

int main()
{
	
	freopen("grigo.in", "r", stdin); 
	freopen("grigo.out", "w", stdout);
	
	scanf("%d%d",&n,&k);
	
	for(int i=1;i<=k;++i)
	{
		scanf("%d",&x);
		vizibil[x] = true ;
	}
	
	long long sol = 1 ;
	for(int i=1;i<=n;++i)
		if ( vizibil[i] == false )
			sol = sol * (i - 1) % MOD ;
		
	printf("%lld\n",sol);
	
	return 0;
	
}