#include<stdio.h>
char marc[100002];
long dinamic[100002];
int x,y,i,n,m;
int main()
{
  freopen("grigo.in","r",stdin);
  freopen("grigo.out","w",stdout);
  scanf("%d %d",&n,&m);
  dinamic[1]=1;
  for(i=1;i<=m;i++)
    {
      scanf("%d",&x);
      marc[x]=1;
    }
  for(i=2;i<=n;i++)
   {
    dinamic[i]=dinamic[i-1];
    if (!marc[i])
       {
	dinamic[i]=(dinamic[i]*(i-1))%1000003;
       }
   }
  printf("%d \n",dinamic[n]);
  return 0;
}