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