#include<cstdio>

const int NMAX=100000;
const int MODULO=1000003;

int f[NMAX+1];

int main()
{
 FILE *fin=fopen("grigo.in","r");

 int n,m;
 fscanf(fin,"%d %d ",&n,&m);
 for(int i=1;i<=m;i++)
    {
     int x;
     fscanf(fin,"%d ",&x);
     f[x]=1;
    }
 fclose(fin);

 long long rez=1;
 for(int i=1;i<=n;i++)
    {
     if(f[i]==0)
        rez=(rez*(i-1))%MODULO;
    }

 FILE *fout=fopen("grigo.out","w");

 fprintf(fout,"%lld\n",rez);
 fclose(fout);
return 0;
}