#include <stdio.h>

int a[100001],n,m;
long long prec,now;


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()
  {
   prec=1;
   for (int i=2;i<=n;i++)
        {if (a[i]==0) now=(prec*(i-1))%1000003;
                 else now=prec;
         prec=now;
         }
   }

void afiseaza()
  {FILE *f;
   f=fopen("grigo.out","w");
   fprintf(f,"%lld",now);
   fclose(f);
   }

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