#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

ifstream fin ("grigo.in");
ofstream fout ("grigo.out");

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

int v[NMAX];

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    int n,m,i;
    long long kon=1;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int x;
        fin>>x;
        v[x]=x;
    }
    for(i=2;i<=n;i++)
    {
        if(!v[i])
        {
            kon=1LL*kon*(i-1);
            kon%=MOD;
        }
    }
    fout<<kon;
    fin.close();
    fout.close();
    return 0;
}