#include <cstdio>
#include <algorithm>
#define MOD 1000003
using namespace std;
FILE *f=fopen("grigo.in","r");
FILE *g=fopen("grigo.out","w");
int N,M;
int V[100005];
int fact[100005];
int lgpow(int b,int e)
{
    int p=1;
    while(e)
    {
        if(e&1)p=(1LL*p*b)%MOD;
        b=(1LL*b*b)%MOD;
        e>>=1;
    }
    return p;
}
int C(int N,int M)
{
    return (1LL*((1LL*fact[N]*lgpow(fact[M],MOD-2))%MOD)*lgpow(fact[N-M],MOD-2))%MOD;
}
int solve(int N,int M)
{
    if(!M)return 1;
    return (1LL*((1LL*solve(V[M]-1,M-1)*C(N-1,V[M]-1))%MOD)*fact[N-V[M]])%MOD;
}
int main()
{
    fact[0]=1;
    for(int i=1;i<=100000;i++)
        fact[i]=(1LL*i*fact[i-1])%MOD;
    fscanf(f,"%d %d",&N,&M);
    for(int i=1;i<=M;i++)fscanf(f,"%d",&V[i]);
    sort(V+1,V+1+M);
    if(V[1]!=1){fprintf(g,"0");return 0;}
    fprintf(g,"%d",solve(N,M));
    fclose(f);
    fclose(g);
    return 0;
}