#include<stdio.h>
long long pm[100005],j,i,n,m,M=1000003,sol=1,K,N;
void hd(long long ic,long long nc);
void sh(long long i1,long long i2);
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",&pm[i]);
        for(i=m/2;i>=1;i--)hd(i,n);
        for(i=m;i>=1;i--){sh(1,i);hd(1,i-1);}
        K=n-pm[m];N=n-1;
        for(i=1;i<=K;i++){sol=(sol*N)%M;N--;}
        for(i=m;i>=1;i--)
        { K=pm[i]-pm[i-1]-1;N=pm[i]-1;
          for(j=1;j<=K;j++){sol=(sol*N)%M;N--;}
        }
        printf("%lld",sol);
        return 0;
}
void sh(long long i1,long long i2)
{
       long long aux=pm[i1];pm[i1]=pm[i2];pm[i2]=aux;
}
void hd(long long ic,long long nc)
{
        long long is,is1;
        is=2*ic;is1=is+1;
        if(is>nc)return;
        if(is<nc) if(pm[is]<pm[is1]) is=is1;
        if(pm[ic]<pm[is]){sh(is,ic);hd(is,nc);}
}