//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]

//ok, idee simpla, merita reluata si aici (ultimul edu div.2D avea
//aceeasi idee)
//luam problema de coada si in loc sa adaugam elemente
//in setul nostru de valori, stergem elemente
//daca pozitia noastra e vizibila, atunci trebuie sa luam din set
//maximul, asadar exista un singur mod de a lua maximul
//daca pozitia noastra nu e vizibila, atunci trebuie sa luam orice
//in afara de maximum: stiind ca s-au sters n - i elemente, raman
//in set n - (n - i) = i elemente, asadar ai i - 1 posibilitati de a
//lua orice, dar nu maximul

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])
        {
            ans = 1LL * ans * (i - 1) % MOD;
        }
    cout << ans;
}