#include <bits/stdc++.h>
using namespace std;
int fr[100005];
int main()
{
   freopen("grigo.in","r",stdin);
   freopen("grigo.out","w",stdout);
   int n,k,x;
   scanf("%d%d",&n,&k);
   for(int i=1;i<=k;i++)
   {
       scanf("%d",&x);
       fr[x]=1;
   }
   long long prod=1;
   int mod=1000003;
   for(int i=1;i<=n;i++)
    if(fr[i]==0)prod=(prod*(i-1))%mod;
   printf("%lld\n",prod);
    return 0;
}