#include<fstream>

using namespace std;

const char iname[]="grigo.in";
const char oname[]="grigo.out";
const int maxn=100005;
const int mod=1000003;

ifstream f(iname);
ofstream g(oname);

int a[maxn],b[maxn],i,j,n,m,x;

long long t;

int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
        f>>x,b[x]=1;
    a[0]=1;
    for(i=1;i<=n;++i)
        if(b[i])
            a[i]=a[i-1];
        else
            t=(i-1)*a[i-1],t%=mod,a[i]=t;

    g<<a[n]<<"\n";
    f.close();
    g.close();

    return 0;
}