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

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

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