#include <bits/stdc++.h>

using namespace std;

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

const int mod = 1e6 + 3;
const int NMAX = 1e5 + 5;
int N, K, x;
bool ap[NMAX];
long long ans = 1;

int main() {
    fin >> N >> K;
    for(int i = 1; i <= K; ++i) {
        fin >> x;
        ap[x] = true;
    }
    for(int i = 1; i <= N; ++i)
        if(!ap[i])
            ans = ans * (i - 1) % mod;
    fout << ans;
}