#include <cstdio>

const int MOD = 1000003;
const int MAX_N = 100010;

int n, m;
int f[MAX_N];
long long d[MAX_N];

int main()
{
	int x;
	freopen("grigo.in", "r", stdin);
	freopen("grigo.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; scanf("%d", &x), f[x] = 1, ++i);
	
	d[1] = 1;
	for (int i = 2; i <= n; d[i] = (f[i]) ? d[i - 1] : d[i - 1] * (i - 1) % MOD, ++i);
	printf("%lld\n", d[n]);
}