#include <bits/stdc++.h>

#define NM 100002
#define MOD 1000003
#define ll long long

using namespace std;

int p[NM];

ll argm(int n, int k)
{
    if(k == 0)
        return 1;
    if(n == 0)
        return 1;
    ll ans = 1;
    for(int i = n - k + 1; i <= n; i++)
        ans = 1ll * ans * i % MOD;
    return ans;
}

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

int main()
{
    ifstream fin ("grigo.in");
    ofstream fout ("grigo.out");
    int n, m;
    fin >> n >> m;
    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;
}