#include<stdio.h>
#define max 1000003
int n,m,f[100005],d[100005];
FILE *in=fopen("grigo.in","rt"),*out=fopen("grigo.out","wt");
int main ()
{
    int i,x;
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&x);
        f[x]=1;
    }
    d[0]=1;
    for(i=1;i<=n;i++)
        if(f[i])
            d[i]=d[i-1];
        else
            d[i]=((long long)d[i-1]*(i-1))%max;
    fprintf(out,"%d",d[n]);
    return 0;
}