#include <fstream>
#include <bitset>

using namespace std;

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

int n,m,i,j,sol,r=1000003;
int s=0;
bitset<100001> v;

int main () {
    f >> n >> m;
    for (i=1;i<=m;i++) {
        f >> j;
        v[j]=1;
    }
    if (v[1]==1) s=1;
    for (i=1;i<=n;i++)
        if (v[i]==0) s=1LL*s*(i-1)%r;
    g << s << '\n';
    f.close();g.close();
    return 0;
}