#include <fstream>
#include <algorithm>

#define DIM 100010
#define MOD 1000003
using namespace std;

long long f[DIM], v[DIM], sol, n, m, x, y;

long long cmmdc(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    } else {
        long long xa, ya;
        long long r = cmmdc(b, a%b, xa, ya);
        x = ya;
        y = xa - ya*(a/b);
        return r;
    }
}

long long im(long long a, long long n) {
    long long x, y;
    cmmdc(a, n, x, y);
    return (x%n+n)%n;
}

long long comb(long long n, long long k) {
    return f[n] * im(f[k], MOD) % MOD * im(f[n-k], MOD) % MOD;

}

int main () {
    ifstream fin("grigo.in");
    ofstream fout("grigo.out");
    fin>>n>>m;
    for (long long i=1;i<=m;i++)
        fin>>v[i];
    v[++m] = n+1;
    sort(v+1, v+m+1);

    f[0] = 1;
    for (long long i=1;i<=n;i++)
        f[i] = f[i-1] * i % MOD;

    sol = 1;
    for (long long i=m-1;i>=1;i--) {
        sol *= comb(x = v[i+1]-2, y = v[i+1]-v[i]-1);
        sol %= MOD;
        sol *= f[y];
        sol %= MOD;
    }

    fout << sol;

    return 0;
}