#include <bits/stdc++.h>
#warning That's not the baby, that's my baby

typedef long long ll;

using namespace std;

const int mod = 1e6 + 3;
const int NMAX = 1e5;

bool f[NMAX + 5];

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

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int p;
        cin >> p;
        f[p] = true;
    }

    int answer = 1;

    for (int i = 1; i <= n; i++) {
        if (!f[i]) {
            answer = (ll) answer * (i - 1) % mod;
        }
    }

    cout << answer;

    return 0;
}