#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

#define MOD 1000003

int v[100001];
int main()
{
    FILE*fi,*fo;
    fi = fopen("grigo.in","r");
    fo = fopen("grigo.out","w");

    int n, m;
    fscanf(fi,"%d%d", &n, &m);
    for(int i = 0; i < m; i++)
        fscanf(fi,"%d", &v[i]);
    v[m] = n + 1;
    std::sort(v, v+m);
    int r = n;
    long long rez = 1;
    for(int i = m - 1; i >= 0; i--){
        r--;
        int c = v[i + 1] - v[i] - 1;
        while(c > 0){
            rez *= r;
            rez %= MOD;
            r--;
            c--;
        }
    }
    while(r > 0){
        rez *= r;
        rez %= MOD;
        r--;
    }
    fprintf(fo,"%lld", rez);
    fclose(fi);
    fclose(fo);
    return 0;
}