#include <fstream>
using namespace std;

const int MAX_N = 100001;
const int MOD = 1000003;

ifstream in("grigo.in");
ofstream out("grigo.out");

int N, M, p[MAX_N];
bool mark[MAX_N];
int fact[MAX_N];
int C_up = 1, C_down = 1;

void read() {
    in >> N >> M;
    memset(mark + 1, 0, N * sizeof(bool));
    for(int i = 1; i <= M; ++i) {
        in >> p[0];
        mark[p[0]] = true;
    }
    M = 0;
    for(int i = 1; i <= N; ++i)
        if(mark[i])
            p[++M] = i;
}

void init() {
    fact[0] = 1;
    for(int i = 1; i <= N; ++i)
        fact[i] = ((long long)fact[i - 1] * i) % MOD;
}

void solve() {
    for(int i = M; i >= 1; --i) {
        C_up = ((long long)C_up * fact[N - 1]) % MOD;
        C_down = ((long long)C_down * fact[p[i] - 1]) % MOD;
        N = p[i] - 1;
    }
}

inline int power(const int &x, const int &p) {
    if(!p)
        return 1;
    int tmp = power(x, p >> 1);
    tmp = ((long long)tmp * tmp) % MOD;
    if(p & 1)
        return ((long long)tmp * x) % MOD;
    else
        return tmp;
}


int main() {
    read();
    init();
    solve();
    out << ((long long)C_up * power(C_down, MOD - 2)) % MOD << endl;
    return 0;
}