#include <fstream>

using namespace std;

#define MOD 1000003
#define nmax 100004

ifstream f("grigo.in");
ofstream g("grigo.out");

int n,m;
bool viz[nmax];
long long rez;

void citeste(){

    f >> n >> m;

    viz[1] = 1;
    for(int i=1; i<=m; i++){
        int x;
        f >> x;
        viz[x] = 1;
    }

}

void rezolva(){

    rez = 1;

    for(int i=1; i<=n; i++){
        if (viz[i] != 1){
            rez = rez * 1LL*(i-1);
            rez = rez % MOD;
        }
    }

    g << rez << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}