//oftica si durere in suflet
#include <fstream>
#include <vector>
#include <climits>
#define ll long long

using namespace std;

//o pozitie vizibila e a unui numar care este mai mare decat toti
//din fata lui

//e clar ca ultimul capat este v[n]

const int MOD = 1e6 + 3;
const int NMAX = 1e5;

bool v[NMAX + 1];

signed main()
{
    ifstream cin("grigo.in");
    ofstream cout("grigo.out");
    int n, m, i;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        v[x] = 1;
    }
    int cnt = 0;
    int ans = 1;
    for (i = n; i >= 1; i--)
        if (v[i])
        {
            if (cnt != 0)
                ans = 1LL * ans * (n - cnt - i + 1) % MOD;
            cnt++;
        }
    for (i = 1; i <= n - cnt; i++)
        ans = 1LL * ans * i % MOD;
    cout << ans;
}