#include <fstream>
using namespace std;
ifstream fin ("grigo.in");
ofstream fout ("grigo.out");
int n,m,i,x,a[100001];
bool v[100001];
int main () {

    fin>>n>>m;
    for (i=1;i<=m;i++){
        fin>>x;
        v[x]++;
    }
    a[1]++;
    for(i=2;i<=n;i++){
        if(v[i]==1)
            a[i]=a[i-1];
        else
            a[i]=(1LL*(i-1)*a[i-1])%1000003;
    }
    fout<<a[n]<<"\n";

    return 0;
}