#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, x;
        for (i = 1; i <= M; ++i)
             scanf ("%d", &x), A[x] = 1;
        
        V[1] = 1;
        for (i = 2; i <= N; ++i)
            if (A[i]) V[i] = V[i - 1];
               else V[i] = ((i - 1)*V[i - 1]) % MOD;
        
        printf ("%d\n", (int)V[N]);
        
        return 0;
    }