#include <stdio.h>

#define NMAX 100010
#define MOD 1000003
#define LL long long

int N, K;
int p[NMAX];
int fact[NMAX];

inline int MAX(int a, int b) { return (a > b) ? a : b; }

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

	scanf("%d %d", &N, &K);
	
	for (i = 1; i <= K; i++) {
		scanf("%d", &p[i]);
	}
	
	if (p[1] != 1) {
		printf("0\n");
		return 0;
	}
	
	p[K + 1] = N + 1;
	
	fact[0] = 1;
	for (i = 1; i <= N; i++) fact[i] = ((LL) fact[i - 1] * i) % MOD;
	
	int p1 = 1, p2 = 1;
	
	for (i = 1; i <= K; i++) {
		if (p[i + 2] - 2 == 0) continue;
		p1 = ((LL) p1 * fact[ p[i + 1] - 2 ]) % MOD;
		p2 = ((LL) p2 * fact[ p[i] - 1 ]) % MOD;
	}
	
	for (i = 1; i <= MOD; i++) if (((LL) p2 * i) % MOD == 1) break;
	
	p1 = ((LL) p1 * i) % MOD;
	
	printf("%d\n", p1);
	
return 0;
}