#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;
ull res = 1;
bitset<100005> visibles;
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;
}


int main()
{
    f >> n >> m;
    calc_factorial_small(n);
    ft(m)
    {
        f >> x;
        visibles[x] = 1;
    }
    /*for every position
    * if it's visible == position index
    * else it can get values from 1 to i-1, while adding 1 to all previous elements
    */
    ft(n)
        if (visibles[i] == 0)
        {
            res = (res * (i - 1)) % MOD;
        }
    g << res;
    return 0;
}