#include<fstream>

using namespace std;

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

long long n,m,a[100001],sol[100001];

int main()
{   int x,i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {    fin>>x;
         a[x]=1;
    }
    sol[0]=1;
    for(i=1;i<=n;i++)
    {   if(a[i]==0) sol[i]=sol[i-1]*(i-1)%1000003;
          else sol[i]=sol[i-1];
    }
    fout<<sol[n]<<"\n";
    fin.close();
    fout.close();
    return 0;
}