#include <fstream>
using namespace std;
ifstream in("grigo.in");
ofstream out("grigo.out");
const int MODULO=1000003;
int v[100001];
int main()
{
    long long m, n, i, nr, s=1;
    in>>n>>m;
    for (i=1; i<=m; i++)
    {
        in>>nr;
        v[nr-1]=1;
    }
    for (i=1; i<n; i++)
        if (v[i]==0)
            s=(s*i)%MODULO;
    out<<s<<'\n';
    return 0;
}