#include<cstdio>
using namespace std;
long i,n,m,im[100003],x,sol[100003];
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",&x);
                im[x]=1;
        }sol[0]=1;
        for(i=1;i<=n;i++)
        {       if(!im[i])sol[i]=sol[i-1]*(i-1);
                else sol[i]=sol[i-1];
        }
        printf("%ld",sol[n]%1000003);
        return 0;
}