#include<stdio.h>

int n,m,x,viz[100004],i;

int main(){


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

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

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

 for(i=1;i<=m;i++)
  if(!viz[i]){
  fprintf(g,"%d",0);
  return 0;
  }

long long rez=1;

  for(i=m;i<n;i++){
  rez*=(long long)i;
  rez%=(long long)1000003;
  }

fprintf(g,"%lld",rez%1000003);

fclose(f);
fclose(g);

return 0;
}