#include<stdio.h>
#define DIM 100001
#define MOD 1000003
long long m,n,i;
long long v[DIM];


int main(){

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

  long long x;
  for(i=1;i<=m;i++){
    fscanf(f,"%lld",&x);
    v[x]=1;
  }
  for(i=2;i<=n;i++)
    if(v[i]!=0)
      v[i]=(((i-1)%MOD)*v[i-1])%MOD;
    else v[i]=v[i-1];
  FILE*g=fopen("grigo.out","w");
  fprintf(g,"%d",v[n]);
  fclose(g);
  return 0;
}