#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

#define nmax 100010
#define modulo 1000003

int X, v[nmax], N, M;
int sol;


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