#include <fstream>
using namespace std;
ifstream in ("grigo.in");
ofstream out ("grigo.out");
int v[100001];
const int mod=1000003;
int main()
{
    long long n,m,i,s=1,nr;
    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)%mod;
    out<<s;
    return 0;
}