#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef size_t ull;
typedef vector<int> vc;
typedef vector<vector<int>> matrix;
#define ft(n) for(int i=1; i<=n; i++)
#define sp ' '
string file = "grigo";
ifstream f(file + ".in");
ofstream g(file + ".out");

const int MOD = 1000003;
int n, m, x, maxx;
vector<int> vis(1, 0);

vector<int> factorial;
void calc_factorial_small(int n)
{
    factorial.resize(n + 5, 0);
    factorial[0] = 1;
    for (int i = 1; i <= n; i++)
        factorial[i] = (factorial[i - 1] * i) % MOD;
}

ull fast_exp(ull a, ull b, int mod)
{
    if (b == 0)
        return 1;
    else
    {
        ull p = fast_exp(a, b / 2, mod);
        if (b % 2 == 1)
            return (((p * p) % mod) * a) % mod;
        else
            return (p * p) % mod;
    }
}

ull mod_div(ull a, ull b, int mod)
{
    b = fast_exp(b, mod - 2, mod); //modular inverse
    ull res = (a * b) % mod;
    return res;
}

ull C(ull k, ull n)
{
    ull div1 = factorial[n];
    ull div2 = (factorial[k] * factorial[n - k]) % MOD;
    ull res = mod_div(div1, div2, MOD);
    return res;
}

void proc()
{
    //largest position given by vis MUST be occupied by n
    ull visibles = C(vis.size() - 2, n - 1);
    ull invisibles = factorial[n - (vis.size() - 1)];
    g << (visibles * invisibles) % MOD;
}

int main()
{
    f >> n >> m;
    calc_factorial_small(n);
    vis.resize(m + 1, 0);
    ft(m)
        f >> vis[i];
    proc();
    return 0;
}