#include <stdio.h>
#define fin "grigo.in"
#define fout "grigo.out"
#define N 100010
#define mod 1000003
int n,k;
int marc[N],v[N];
int sol[N];
int main(void){
    int i,j;
    freopen(fin,"r",stdin);
    freopen(fout,"w",stdout);
    scanf("%d%d",&n,&k);
    for (i=1;i<=k;++i){
        scanf("%d",&v[k]);
        marc[v[k]]=1;
    }
    sol[1]=1;
    for (i=2;i<=n;++i){
        if (marc[i])
           sol[i]=sol[i-1];
        else
            sol[i]=(sol[i-1]*(i-1))%mod;
    }
    printf("%d\n",sol[n]);
    return 0;
}