#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "grigo.in"
#define FOUT "grigo.out"
#define MAX_N 100005
#define MOD 1000003

int A[MAX_N];
int V[MAX_N];
int N, M;

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        

        scanf ("%d %d", &N, &M);
        int i, j;
        for (i = 1; i <= M; ++i) scanf ("%d", A + i);
        
        V[1] = 1;
        for (i = 2, j = 1; i <= N; ++i)
            if (i == A[j]) V[i] = V[i - 1], ++j;
               else V[i] = ((i - 1)*V[i - 1]) % MOD;
        
        printf ("%d\n", (int)V[N]);
        
        return 0;
    }