#include <stdio.h>

long long n, m, v[100001];
long long mod;

int main()
{
	freopen("grigo.in","r",stdin);
	freopen("grigo.out","w",stdout);

	long long i, x;
	mod = 1000003;
	scanf("%lld %lld",&n,&m);
	for (i = 1; i <= m; i++)
	{
		scanf("%lld",&x);
		v[x] = 1;
	}

	for (i = 2; i <= n; i++)
		if (!v[i]) v[i] = (((i - 1) % mod) * v[i - 1]) % mod;
		else v[i] = v[i - 1];
	printf("%lld\n",v[n]);
	return 0;
}