#include <cstdio>
#include <algorithm>
using namespace std;
const int p=1000003,NMAX=100001;
int v[NMAX],n,m,t[NMAX],s[NMAX];
long long w;
int main(){
    int i,x,y,k,sol=0,a;
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (i=1;i<=m;++i) scanf("%d",&v[i]);
    sort(v+1,v+m+1);
    for (x=v[2]-1;x<=n-m+1;++x) t[x]=1;
    v[m+1]=n+1;
    for (k=2;k<=m;++k){
        for (x=v[k+1]-1;x<=n-m+k;++x){
            s[x]=0;
            for (y=v[k]-1;y<x && y<=n-m+k-1;++y){
             for (a=1,i=0;i<v[k]-v[k-1]-1;++i)
               w=(long long)(a*(y-v[k-1]-i)),a=w%p;
             w=(long long)a*t[y],a=w%p;
             s[x]=(s[x]+a)%p;}
             }
        memcpy(t,s,sizeof(s));
        }    
    sol=t[n]; 
    for (a=1,i=1;i<=n-v[m];i++) 
        w=(long long)a*i,a=w%p;
    w=(long long)sol*a;
    sol=w%p;
    printf("%d",sol);
    return 0;
}