#include <bits/stdc++.h>
#define modulo 1000003

using namespace std;

int a[100005], n, k;

int main()
{
    int i, p;
    long long cnt;
    ifstream fin("grigo.in");
    fin >> n >> k;
    for (i = 1; i <= k; ++i)
    {
        fin >> p;
        a[p] = 1;
    }
    fin.close();

    /// cnt[i] = numarul de posibilitati de a aranja
    /// intr-o permutare valida numerele 1..i
    cnt = 1;
    for (i = 2; i <= n; ++i)
        if (a[i] != 1) cnt = (cnt * (i - 1)) % modulo;

    ofstream fout("grigo.out");
    fout << cnt << "\n";
    fout.close();

    return 0;
}