#include<fstream>
using namespace std;
int n,m,sol;
bool viz[100001];
int mod=1000003;
ifstream in("grigo.in"); ofstream out("grigo.out");
int main(){
    in>>n>>m;
    for(int i=1;i<=m;++i) { in>>sol; viz[sol]=true;}
    sol=1;
    for(int i=1;i<=n;++i)
        if(!viz[i]) sol=(long long)sol*(i-1)%mod;
    out<<sol<<'\n'; out.close(); return 0;
}