#include <cstdio>

#define modulo 1000003
#define Nmax 100001

int N, M, i, p;
char W[Nmax];

int main()
{
 freopen("grigo.in","r",stdin);
 scanf("%d %d",&N,&M);
 for (i=1; i<=N; ++i)
     {
      scanf("%d",&p);
      W[p] = 1;
     }
 for (i=1,p=1; i<=N; ++i)
     if (!W[i]) p = ((long long)p*(i-1)) % modulo;
 freopen("grigo.out","w",stdout);
 printf("%d\n",p);
 fclose(stdout);
 return 0;
}