#include <fstream>

using namespace std;

int main () {
    ifstream fin ("grigo.in");
    ofstream fout ("grigo.out");
    int N, M, lol[100005], a;
    long long sol = 1;
    fin >> N >> M;
    for (int i = 0; i < M; i++)
        fin >> a, lol[a] = 1;
    fin.close ();
    for (int i = 1; i <= N; i++)
        if (!lol[i]) sol = 1LL * (sol * 1LL * (i - 1)) % 1000003;
    fout << sol;
    fout.close ();
    return 0;
}