#include <cstdio>

const int MOD = 1e6 + 3;
const int MAXN = 1e6;

bool v[MAXN + 1];

int main() {
  int n, k, sol, x;
  FILE *f = fopen("grigo.in", "r");
  fscanf(f, "%d%d", &n, &k);
  for (int i = 0; i < k; ++i) {
    fscanf(f, "%d", &x);
    v[x] = 1;
  }
  fclose(f);
  sol = 1;
  for (int i = 1; i <= n; ++i) {
    if (!v[i]) {
      sol = 1LL * sol * (i - 1) % MOD;
    }
  }
  f = fopen("grigo.out", "w");
  fprintf(f, "%d\n", sol);
  fclose(f);
  return 0;
}