#include<cstdio>
#include<algorithm>
#include<fstream>
using namespace std;
ifstream f("grigo.in");
int n,m,spec[1<<17],d[1<<17];
const int MOD=1000003;
void read()
{
    freopen("grigo.out","w",stdout);
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>spec[i];
    sort(spec+1,spec+m+1);
    if(spec[1]!=1)
        printf("0");
}
void solve()
{
    int q=2;
    d[1]=1;
    for(int i=2;i<=n;i++)
        if(i==spec[q])
            d[i]=d[i-1], ++q;
        else
            d[i]=((long long)(i-1)*d[i-1])%MOD;
}
int main()
{
    read();
    solve();
    printf("%d",d[n]);
    return 0;
}