#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 1 << 17;
const int MOD = 1000003;
int N, M, R, A[NMAX];
void read(void) {
ifstream fin("grigo.in");
int i;
fin >> N >> M;
for (i = 0; i < M; ++i)
fin >> A[i];
sort(A, A + M);
fin.close();}
void solve(void) {
int i, j, v;
A[M] = N + 1; R = 1;
for (i = M - 1; i >= 0; --i) {
for (v = A[i+1] - 2, j = A[i + 1] - A[i]; j > 1; --j, --v)
R = ((long long) R * v) % MOD;  }}
void write(void) {
ofstream fout("grigo.out");
if (A[0] != 1) R = 0;
fout << R << '\n';
fout.close();
}
int main(void) {
read();
solve();
write();
return 0;
}