#include<cstdio>

using namespace std;

const int nmax=1e5+5;
const int mod=1e6+3;

long long dp[nmax];
bool viz[nmax];

int main()
{
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);
    long long n,i,m;
    scanf("%lld%lld",&n,&m);;
    int a;
    for(i=1;i<=m;i++)
        scanf("%d",&a),viz[a]=1;
    dp[1]=1;
    for(i=2;i<=n;++i)
        if(viz[i])
            dp[i]=dp[i-1];
        else
            dp[i]=((i-1)*dp[i-1])%mod;
    printf("%lld",dp[n]);
}