#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
 
using namespace std;

#define MAXN 100005
#define MOD 1000003

int n, m;

bool isVisible[MAXN];

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

	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; ++i) {
		int x;
		scanf("%d", &x);
		isVisible[x] = true;
	}

	int s = 1;

	for (int i = 1; i <= n; ++i) {
		if (!isVisible[i]) {
			s *= (i - 1);
			s %= MOD;
		}
	}

	printf("%d", s);

	return 0;
}