#include<fstream>

using namespace std;

ifstream f("grigo.in");
ofstream g("grigo.out");
int n,m,x,nr[100100];
bool viz[100100];
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i){
        f>>x;
        viz[x]=1;
    }
    nr[1]=1;
    for(int i=2;i<=n;++i){
        if(viz[i]==1) nr[i]=nr[i-1];
        else nr[i]=nr[i-1]*(i-1);
        nr[i]%=1000003;
    }
    g<<nr[n]<<'\n';


}