#include <bits/stdc++.h>

using namespace std;

char vf[100001];
const int MOD = 1000003;

int main()
{
    FILE *fi = fopen("grigo.in", "r"), *fo = fopen("grigo.out", "w");
    int n, k, i, j, nr, x;
    fscanf(fi, "%d%d", &n, &k);
    for(i = 0; i < k; i++){
        fscanf(fi, "%d", &x);
        vf[x - 1] = 1;
    }
    /*sort(poz, poz + k);
    nr = 1;
    poz[k] = n + 1;
    for(i = k - 1; i >= 0; i--){
        poz[i + 1]--;
        for(j = poz[i] + 1; j < poz[i + 1]; j++)
            nr = (1LL * nr * j) % MOD;
    }*/
    nr = 1;
    for(i = 1; i < n; i++)
        if(vf[i] == 0)
            nr = (1LL * nr * i) % MOD;
    fprintf(fo, "%d", nr);
    return 0;
}