#include <bits/stdc++.h>

#define NM 100002
#define MOD 1000003

using namespace std;

int pwr(int a, int b)
{
    if(b == 0)
        return 1;
    int p = pwr(a, b / 2);
    if(b % 2 == 0)
        return 1ll * p * p % MOD;
    else
        return 1ll * p * p % MOD * a % MOD;
}

int inv[NM];
int fact[NM], ifact[NM];
int p[NM];

int argm(int n, int k)
{
    if(k < n / 2)
        k = n - k;
    return 1ll * fact[n] * ifact[n - k] % MOD;
}

int solve(int n, int m)
{
    if(n == 0)
        return 1;
    if(m == 0)
        return fact[n];
    return solve(p[m] - 1, m - 1) * argm(n - 1, n - p[m]);
}

int main()
{
    ifstream fin ("grigo.in");
    ofstream fout ("grigo.out");
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= n; i++)
        inv[i] = pwr(i, MOD - 2);
    fact[0] = 1;
    ifact[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        fact[i] = 1ll * fact[i - 1] * i % MOD;
        ifact[i] = 1ll * ifact[i - 1] * inv[i] % MOD;
    }
    for(int i = 1; i <= m; i++)
        fin >> p[i];
    sort(p + 1, p + m + 1);
    if(p[1] == 1)
        fout << solve(n, m);
    else
        fout << "0\n";
    return 0;
}