#include <iostream>
#include <fstream>
using namespace std;
const long long mod=1000003;
long long pos,i;
int n,m,x;
bool ap[100005];
int main()
{
    ifstream f("grigo.in");
    ofstream g("grigo.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x;
        ap[x]=1;
    }
    pos=1;
    for(i=1;i<=n;i++)
    {
        if(!ap[i]) pos=1LL*(pos*(i-1))%mod;
    }
    g<<pos;
    return 0;
}