#include <stdio.h>

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

int N, K, rez = 0;
int p[NMAX];
//char poz[NMAX];
//int a[NMAX];
//char viz[NMAX];

int fact[NMAX];

inline int MAX(int a, int b) { return (a > b) ? a : b; }
/*
void back(int k, int mx)
{
	if (k == N + 1) {
		rez++;
		return;
	}
	
	int i;
	
	for (i = 1; i <= N; i++) {
		if (viz[i]) continue;
		if ((i > mx) != poz[k]) continue;
		
		a[k] = i; viz[i] = 1;
		back(k + 1, MAX(mx, i));
		viz[i] = 0;
	}
}
*/
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]);
//		poz[p[i]] = 1;
	}
	
	p[K + 1] = N + 1;
	
	fact[0] = 1;
	for (i = 1; i <= N; i++) fact[i] = ((LL) fact[i - 1] * i) % MOD;
	
//	back(1, 0);
	
//	printf("%d\n", rez);
	
	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;
	}
	
//	printf("%d %d\n", p1, p2);
	
	for (i = 1; i <= MOD; i++) if (((LL) p2 * i) % MOD == 1) break;
	
	p1 = ((LL) p1 * i) % MOD;
	
	printf("%d\n", p1);
	
return 0;
}