#include <fstream.h>
#include <iostream.h>
fstream f("grigo.in", ios::in);
fstream g("grigo.out", ios::out);

int v[100001];
int main ()
{
 long m,n,i,j;
 int x;

 f>>n>>m;
 for(i=1;i<=m;i++)
    {
     f>>x;
     v[x]=1;
     }

 for(i=2;i<=n;i++)
    {
     if(v==0) v[i]=(v[i-1]*((i-1)%1000003))%1000003;
	else v[i]=v[i-1];
     }
 g<<v[n];

 f.close();
 g.close();

 return 0;

}