#include <cstdio>

using namespace std;

const int MaxN = 100005;
const int Mod = 1000003;

int N, S;
bool Visible[MaxN];

void Solve() {
    S = 1;
    for (int i = 2; i <= N; ++i)
        if (!Visible[i])
            S = (1LL*S*(i-1))%Mod;
}

void Read() {
    freopen("grigo.in", "r", stdin);
    int M; scanf("%d %d", &N, &M);
    for (; M; --M) {
        int P; scanf("%d", &P);
        Visible[P] = true;
    }
}

void Print() {
    freopen("grigo.out", "w", stdout);
    printf("%d\n", S);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}