# include <stdio.h>
# define max 100002

int n,m,x,i;
char indice[max];
long long NrSol[max];

int main() {   
    freopen("grigo.in","r",stdin);   
    freopen("grigo.out","w",stdout);   
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
        {
          scanf("%d", &x);  
          indice[x]=1;
        }
    NrSol[1]=1;
    for(i=2;i<=n;i++)
    {
      NrSol[i]=NrSol[i-1];
      if (!indice[i])
                 NrSol[i]=(NrSol[i]*(i-1))%1000003; 
    }
    printf("%d",NrSol[n]);
  return 0;    
}