#include <bits/stdc++.h>

using namespace std;

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

const int mod = 1e6 + 3;
long long ans = 1;
int n, k, v[100002];

int main()
{
  fin >> n >> k;
  for (int i = 1; i <= k; i++) {
    int x;
    fin >> x;
    v[x] = 1;
  }
  for (int i = 1; i <= n; i++)
    if (!v[i])
      ans = ans * (i - 1) % mod;
  fout << ans;
  return 0;
}