#include <fstream>
using namespace std;
ifstream f("grigo.in"); ofstream g("grigo.out");
int n,m,x,i,nr[1000001];
bool ok[1000001];
int main ()
{   f>>n>>m;
    for(i=1;i<=m;++i) f>> x, ok[x]=true;
    nr[0] = 1;
    for(i=1;i<=n;++i)
        if(ok[i]) nr[i]=nr[i-1]; else nr[i]=(1LL*(i - 1)*nr[i-1])%1000003;
	g<<nr[n]; g.close(); return 0;
}