#include <iostream>
#include <cstdio>
#define MAXN 100050
#define MOD 1000003

using namespace std;

int n, m, a[MAXN], din[MAXN];

void solve()
{
    din[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (a[i])
            din[i] = din[i-1];
        else
            din[i] = (1LL*(i-1) * din[i-1]) % MOD;
    }
}

int main()
{
    freopen("grigo.in", "r", stdin);
    freopen("grigo.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x;
        scanf("%d", &x);
        a[x]++;
    }
    solve();
    printf("%d", din[n]);

    return 0;
}