#include <fstream>
#include <algorithm>

using namespace std;

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

const int nmax = 1e5;
const int mod = 1000003;

int v[nmax + 1];
bool ok[nmax + 1];

int main() {
    int n, m;

    fin >> n >> m;
    for (int i = 0; i < m; ++ i) {
        int x;
        fin >> x;
        ok[ x ] = 1;
    }

    long long ans = 1;
    for (int i = 1; i <= n; ++ i) {
        if (ok[ i ] == 0) {
            ans = ans * (i - 1) % mod;
        }
    }
    fout << ans << "\n";
    return 0;
}