#include <fstream>

using namespace std;

int main () {
    ifstream fin ("grigo.in");
    ofstream fout ("grigo.out");
    int N, M, lol[100005], sol = 1, a;
    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 = (sol * (i - 1)) % 1000003;
    fout << sol;
    fout.close ();
    return 0;
}