#include <cstdio>

const int MAX_SIZE(100001);
const int MOD(1000003);

bool visible [MAX_SIZE];

int main (void)
{
	std::freopen("grigo.in","r",stdin);
	std::freopen("grigo.out","w",stdout);
	int n, m;
	std::scanf("%d%d",&n,&m);
	int position, *position_ptr(&position);
	do
	{
		std::scanf("%d",position_ptr);
		visible[position] = true;
		--m;
	}
	while (m);
	std::fclose(stdin);
	unsigned long long permutations(1);
	for (bool *iterator(visible + 3), *end(visible + n) ; iterator <= end ; ++iterator)
		if (*iterator) // must remain there
			continue;
		else           // must replace any previous value
			permutations = permutations * (iterator - visible - 1) % MOD;
	std::printf("%llu\n",permutations);
	std::fclose(stdout);
	return 0;
}