#include <iostream>
#include <fstream>
 
using namespace std;
 
ifstream in ("grigo.in");
ofstream out ("grigo.out");
 
const int MAXN = 100010;
const int MOD = 1000003;
 
long long Sol[MAXN];
bool visible[MAXN];
 
int main ()
{
    int N, M, x, i;
 
    in >> N >> M;
 
    for (i = 1; i <= M; i ++)
        in >> x, visible[x] = 1;
 
    Sol[0] = 1;
    for (i = 1; i <= N; i ++)
        if (visible[i])
            Sol[i] = (1LL * Sol[i - 1]) % MOD;
        else
            Sol[i] = (1LL * (long long) (i - 1) * Sol[i - 1]) % MOD;
 
    out << (Sol[N] % MOD);
 
    return 0;
}