#include <bits/stdc++.h>

const int MAXN = (int) 1e5;
const int MOD = (int) 1e6 + 3;

bool ok[MAXN + 1];

int main() {
    FILE *fi, *fout;
    int i, n, m, pos;
    fi = fopen("grigo.in" ,"r");
    fout = fopen("grigo.out" ,"w");
    fscanf(fi,"%d %d " ,&n,&m);
    for(i = 1; i <= m; i++) {
        fscanf(fi,"%d " ,&pos);
        ok[pos] = 1;
    }
    int ans = 1;
    for(i = 1; i <= n; i++)
        if(!ok[i])
            ans = (1LL * ans * (i - 1)) % MOD;
    fprintf(fout,"%d" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}