#include <fstream>

using namespace std;

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

const int nmax= 100000;
const int mod= 1000003;

bool u[nmax+1];

int main(  ) {
    int n, m;
    fin>>n>>m;
    for ( int i= 1; i<=m; ++i ) {
        int x;
        fin>>x;
        u[x]= 1;
    }

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

    return 0;
}