#include<cstdio>
using namespace std;
int i,n,k,val,mod,ap[100009];
long long p;
int main()
{
freopen("grigo.in","r",stdin);
freopen("grigo.out","w",stdout);
mod=1000003;
scanf("%d",&n);
scanf("%d",&k);
p=1;
while(k)
{
    k--;
    scanf("%d",&val);
    ap[val]=1;
}
for(i=1;i<=n;i++)
    if(ap[i]==0) p=(1LL*p*(i-1))%mod;
printf("%lld\n",p);
return 0;
}