#include <stdio.h>
#include <algorithm>
using namespace std;
#define fin "grigo.in"
#define fout "grigo.out"
#define N 15
#define mod 1000003
int n,k;
int x[N],v[N];
int marc[N];
int main(void){
    int i,j,bun,sw,s,sol=0;
    freopen(fin,"r",stdin);
    freopen(fout,"w",stdout);
    scanf("%d%d",&n,&k);
    for (i=1;i<=k;++i){
        scanf("%d",&x[k]);
        marc[x[k]]=1;
    }
    sort(x+1,x+k+1);
    for (i=1;i<=n;++i)
        v[i]=i;
        int ok;
    do{
        s=1;ok=1;
        for (i=2;i<=n;++i){
            sw=1;bun=1;
            for (j=1;j<i;++j)
                if (v[j]>v[i])
                   sw=0;
            if ((marc[i]==1 && !sw) || (marc[i]==0))
               bun=0;
            if ((marc[i]==0 && sw )|| (marc[i]==1 && !sw))
               ok=0;
            if (bun)
               ++s;
        }
        //for (i=1;i<=n;++i)
            //printf("%d ",v[i]);
        //printf("\t%d %d\n",s,bun);
        if (ok==0 || s!=k)
           s=0;
        if (s)
           sol=(sol+1)%mod;
    }while (next_permutation(v+1,v+n+1));
    printf("%d\n",sol);
    return 0;
}