#include <cstdio>
#include <algorithm>
using namespace std;

const int MOD = 1000003;
const int N = 100000;

int n,m;
int p[N];
int d[N];

int main() {
	freopen("grigo.in","rt",stdin);
	freopen("grigo.out","wt",stdout);
	scanf("%d %d",&n,&m);
	for (int i = 0; i < m; ++i) {
		scanf("%d",&p[i]);
		--p[i];
	}
	sort(p,p+m);
	d[0] = 1;
	for (int i = 1, t = 1; i < n; ++i) {
		if (i == p[t]) {
			d[i] = d[i-1];
			++t;
		} else {
			d[i] = ((long long)i*d[i-1]) % MOD;
		}
	}
	printf("%d\n",d[n-1]);
	return 0;
}