# 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;      
}