#include <stdio.h>
#define MAXN 100000
#define MOD 1000003
int v[MAXN + 1];

inline void prod(int num, int nr, long long *rez){
  int i;
  for(i = num; num - i + 1 <= nr; i--){
    *rez *= i;
    *rez %= MOD;
  }
}

int main(){
  FILE *in = fopen("grigo.in", "r");
  int n, m, i, x;
  fscanf(in, "%d%d", &n, &m);
  for(i = 0; i < m; i++){
    fscanf(in, "%d", &x);
    v[x] = 1;
  }
  fclose(in);
  long long rez = 1;
  int num = n, nr = 0;
  for(i = n; i > 0; i--){
    if(v[i] == 1){
      num--;
      prod(num, nr, &rez);
      num -= nr;
      nr = 0;
    }
    else
      nr++;
  }
  if(nr > 0)
    rez = 0;
  FILE *out = fopen("grigo.out", "w");
  fprintf(out, "%d", rez);
  fclose(out);
  return 0;
}