#include <bits/stdc++.h>

using namespace std;

ifstream fin("grigo.in");
ofstream fout("grigo.out");

const int mod = 1000003;

int main() {
  int n, m;
  fin >> n >> m;
  vector<bool>mus(n + 1);

  for (int i = 1, x; i <= m; ++i) {
    fin >> x;
    mus[x] = 1;
  }

  vector<int>dp(n + 1);
  dp[0] = 1;

  for (int i = 1; i <= n; ++i) {
    if (mus[i]) dp[i] = dp[i - 1];
    else dp[i] = (1LL * dp[i - 1] * (i - 1)) % mod;
  }

  fout << dp[n];
}