#include<stdio.h>

long long n,m,x,viz[100004],a[100004],i;

int main(){


FILE *f=fopen("grigo.in","r");
fscanf(f,"%lld %lld",&n,&m);

 for(i=1;i<=m;i++){
 fscanf(f,"%lld ",&x);
 viz[x]=1;
 }

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

a[1]=1;

  for(i=2;i<=n;i++){

    if(viz[i]){
    a[i]=a[i-1];
    }

    else{
    a[i]=(a[i-1]*(i-1))%1000003;
    }
    
  }

fprintf(g,"%lld",a[n]);

fclose(f);
fclose(g);

return 0;
}