#include<cstdio>
#define MOD 1000003

using namespace std;

int i,n,m,x,v[100002],nr;

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