#include <cstdio>
#define NMax 100000

const int MOD = 1000003;

char ap[NMax+1];
int fact[NMax+1];
int v[NMax+1];
int N,M;

void Read()
{
    int i,x;

    scanf("%d %d",&N,&M);
    for(i = 1; i <= M; ++i)
    {
        scanf("%d",&x);
        ap[x] = 1;
    }

    for(M = 0, i = NMax; i >= 1; --i)
    if( ap[i] ) v[++M] = i;
    v[0] = N+1;

    fact[0] = 1;
    for(i = 1; i <= NMax; ++i) fact[i] = ( fact[i-1] * i ) % MOD;
}

int lgput(int X, int B)
{
    int A=1;
    while(B>1)
    {
        if(B%2) A=(1LL*A*X)%MOD;
        X=(1LL*X*X)%MOD;
        B/=2;
    }
    return ( 1LL * A * X )%MOD;
}

int Aranj(int N, int K)
{
    if(!K || !N) return 1;
    return ( 1LL * fact[N] * lgput( fact[N-K], MOD-2) ) % MOD;
}

int main(){
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);

    int i,ans=1;

    Read();
    if( !ap[1] ) ans = 0;
    else
    {
        for(--N, i = 1; i <= M; ++i)
        {
            ans = ( 1LL * ans * Aranj(N, v[i-1] - v[i] - 1) ) % MOD;
            N -= v[i-1] - v[i];
        }
    }

    printf("%d\n",ans);



return 0;
}