#include <bits/stdc++.h>

#define MaxN 100005
#define INF 2140000000
#define MOD 1000003

using namespace std;

FILE *IN,*OUT;

int N,M,v[MaxN],ans=1,fact[MaxN];

int lgpow(int base,int exp)
{
    int aux=1;
    for(int i=0;i<=20;i++)
    {
        if((1<<i)&exp)
            aux=1LL*aux*base%MOD;
        base=1LL*base*base%MOD;
    }
    return aux;
}
int Arrangements(int n,int k)
{
    return 1LL*fact[n]*lgpow(fact[n-k],MOD-2)%MOD;
}

int main()
{
    IN=fopen("grigo.in","r");
    OUT=fopen("grigo.out","w");

    fscanf(IN,"%d%d",&N,&M);

    for(int i=1;i<=M;i++)
        fscanf(IN,"%d",&v[i]);

    fact[0]=1;
    for(int i=1;i<=N;i++)
        fact[i]=1LL*fact[i-1]*i%MOD;

    v[++M]=N+1;

    for(int i=M-1;i>0;i--)
        ans=1LL*ans*Arrangements(v[i+1]-2,v[i+1]-v[i]-1)%MOD;

    fprintf(OUT,"%d",ans);

    return 0;
}