#include <cstdio>
using namespace std;
const int NMAX = 100005;
const int MOD = 1000003;
bool vf[NMAX];

int main() {
  int n, m;
  freopen("grigo.in", "r", stdin);
  freopen("grigo.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    int x;
    scanf("%d", &x);
    vf[x] = 1;
  }
  long long int sol = 1;
  for(int i = 1; i <= n; ++i) {
    if(!vf[i]) {
      sol = (sol * (i - 1)) % MOD;
    }
  }
  printf("%lld\n", sol);
  return 0;
}