#include <stdio.h>

int a[100001],n,m;
long long sol[100001];


void citire()
 {int x;
  FILE *f;
  f=fopen("grigo.in","r");
  fscanf(f,"%d %d",&n,&m);
  for (int i=0;i<m;i++)
     {fscanf(f,"%d",&x);
      a[x]=1;
      }
  fclose(f);
  }

void calculeaza()
  {
   sol[1]=1;
   for (int i=2;i<=n;i++)
        if (a[i]==0) sol[i]=(sol[i-1]*(i-1))%1000003;
                else sol[i]=sol[i-1];
   }

void afiseaza()
  {FILE *f;
   f=fopen("grigo.out","w");
   fprintf(f,"%d",sol[n]);
   fclose(f);
   }

int main()
 {
  citire();
  calculeaza();
  afiseaza();
  return 0;
  }