#include<cstdio>

using namespace std;

long long i,n,m,im[100010],x,sol[100010];

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