#include<stdio.h>   
#define Nmax 100010
#define MOD 1000003

long n,m,i,rez=1,v[Nmax],a;

int main()
{
freopen("grigo.in","rt",stdin);
freopen("grigo.out","wt",stdout);
scanf("%ld %ld",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%ld",&a);
v[a]=1;
}
for(i=1;i<=n;i++)
{
if (v[i]==1) continue;
rez*=(i-1);
rez%=MOD;
}
printf("%ld",rez);
return 0;
}