#include<cstdio>
using namespace std;
bool ap[100005];
int main()
{
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);
    long long n,k,x,ans=1;
    scanf("%lld%lld",&n,&k);
    for(register int i=1;i<=k;i++)
    {
        scanf("%d",&x);
        ap[x]=1;
    }
    for(register int i=1;i<=n;i++)
        if (ap[i]==0) ans=(ans*(i-1))%1000003 ;
    printf("%lld",ans);
}