#include<cstdio>
#define MOD 1000003

using namespace std;

int viz[1000004],n,m,nr,i,x;

int main()
{
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);
    nr=1;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&x);
        viz[x]=1;
    }
    for (i=1;i<=n;i++)
    {
        if (viz[i]==1)
            continue;
        nr*=i-1;
        nr%=MOD;
    }
    printf("%d\n",nr);
    return 0;
}