#include <stdio.h>

int n, m, v[100001];
const int mod = 1000003;

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

	int i, x;
	scanf("%d %d",&n,&m);
	for (i = 1; i <= m; i++)
	{
		scanf("%d",&x);
		v[x] = 1;
	}

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