#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 1e5, MOD = 1000003;

int n, m;
long long ans[NMAX + 5];
bool viz[NMAX + 5];

int main()
{
    in >> n >> m;
    while(m--)
    {
        int pos;
        in >> pos;
        viz[pos] = true;
    }

    ans[1] = viz[1];
    for(int i = 2; i <= n; i++)
    {
        ans[i] = ans[i - 1];
        if(!viz[i])
            ans[i] = (1LL * ans[i] * (i - 1)) % MOD;
    }

    out << ans[n] << '\n';

    return 0;
}