#include<stdio.h>
#define nmax 100024
bool ok[nmax];
long long sol[nmax];
const int much=1000003;
int main()
{freopen("grigo.in","r",stdin);
 freopen("grigo.out","w",stdout);
 int N,M;
 scanf("%d%d\n",&N,&M);
 int i,a1;sol[1]=1;
 while( M-- ){
 scanf("%d",&a1);
 ok[a1]=true;
 }
 for(i=2; i<=N; ++i){
          if( ok[i] )
          sol[i]=sol[i-1];
          else
          sol[i]=(long long)sol[i-1]*(i-1)%much;
 }
 printf("%lld\n",sol[N]);
    return 0;
}