#include<stdio.h>
#define ll long long
#define MOD 1000003
int n,m,f[100005],d[100005];
int main ()
{
    int i,x;
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);
    scanf("%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]=((ll)d[i-1]*(i-1))%MOD;
    printf("%d\n",d[n]);
    return 0;
}