#include <cstdio>

using namespace std;

long n,m,i,j,v[100100],x[100100],mod;

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