#include <fstream>

using namespace std;

ifstream cin ("grigo.in");
ofstream cout ("grigo.out");

const int MOD = (int)1e6 + 3;

int n, m, sol, x;

bool f[100005];

int main() {
  cin >> n >> m >> x;
  if(x != 1) {
    cout << 0;
    return 0;
  }
  for(int i = 1; i < m; i++)
    cin >> x, f[x] = 1;
  sol = 1;
  for(int i = 2; i <= n; i++)
    sol = 1LL * sol * (!f[i] ? i - 1 : 1) % MOD;
  cout << sol;
  return 0;
}