#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;}