#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 100005
#define MOD 1000003

int N, M, poz[MAXN];
int fac[MAXN];

int gcd( int a, int b, int &x, int &y )
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}

	int x0, y0;
	int d = gcd( b, a % b, x0, y0 );
	x = y0;
	y = x0 - (a / b) * y0;
	return d;
}

inline int moduloMul( int a, int b )
{
	int rez = (int)((long long)a * b) % MOD;
	if (rez < 0)
		rez += MOD;
	return rez;
}

inline int moduloDiv( int a, int b )
{
	int d, x, y;
	d = gcd( b, MOD, x, y );

	return moduloMul(a, x);
}

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", poz + i);
	poz[M] = N + 1;
	sort( poz, poz + M );

	fac[0] = 1;
	for (int i = 1; i <= N; i++)
		fac[i] = moduloMul( fac[i - 1], i );

	int Rez = 1;
	if (poz[0] != 1)
	{
		printf("0\n");
		return 0;
	}
	for (int i = M - 1; i >= 0; i--)
	{
		//pe poz[i] pun cea mai mare valoare din cele ramase
		//Rez *= aranjamente de (poz[i + 1] - 2) luate cate (poz[i + 1] - poz[i] - 1)
		Rez = moduloMul( Rez, fac[poz[i + 1] - 2] );
		Rez = moduloDiv( Rez, fac[poz[i] - 1] );
	}

	printf("%d\n", Rez);

	return 0;
}