#include<cstdio>
const int MOD = 1000003;
using namespace std;

int i , n , k , a;
bool viz[100005];
long long int ans = 1;

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