#include<stdio.h>
#define MOD 1000003
#define N 100000
int poz[N];
int main(){
    FILE *fin,*fout;
    fin=fopen("grigo.in","r");
    fout=fopen("grigo.out","w");
    int n,m;
    fscanf(fin,"%d%d",&n,&m);
    int i;
    for(i=0;i<m;i++){
        int nr;
        fscanf(fin,"%d",&nr);
        poz[nr-1]=1;
    }
    int rasp=1;
    for(i=0;i<n;i++)
        if(poz[i]==0)
            rasp=((long long)rasp*i)%MOD;
    fprintf(fout,"%d",rasp);
    return 0;
}