#include<stdio.h>
long n,m,i,aa;
long long a[100005];
int main()
{
 freopen("grigo.in","r",stdin);
 freopen("grigo.out","w",stdout);
 scanf("%ld%ld",&n,&m);
 for(i=1;i<=m;++i)
    {scanf("%ld",&aa);a[aa]=1;}
 a[0]=1;
 for(i=1;i<=n;++i)
    if(a[i]!=1){a[i]=(a[i-1]*(i-1))%1000003;}
      else a[i]=a[i-1];
 printf("%lld\n",a[n]);
 return 0;
}