# include <stdio.h>

# define FIN "grigo.in"
# define FOUT "grigo.out"
# define MAXN 100001
# define INF 1000003

int precalc[MAXN];
unsigned char s[MAXN];
int N,M,i;

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%d%d",&N,&M);
        int x;
        for (i = 1; i <= N; ++i)
          {
              scanf("%d",&x);
              s[x]=1;
          }
        precalc[0]=1;
        for (i = 1; i <= N; ++i)
          if (s[i]==1) precalc[i]=precalc[i-1];
          else precalc[i]=((i-1)*(precalc[i-1]%INF))%INF;
          
        printf("%d",precalc[N]);
        
        return 0;
    }