#include <fstream>
using namespace std;

ifstream cin("grigo.in");
ofstream cout("grigo.out");

constexpr int NMAX = 1e5 + 1;
constexpr int MOD = 1e6 + 3;
bool avem[NMAX];

int main()
{
    int n,m,x,ans = 1; cin >> n >> m;
    for(int i = 0 ; i < m ; i++) cin >> x,avem[x] = 1;
    for(int i = 1; i <= n ; i++)
        if(!avem[i]) ans = 1LL * ans * (i - 1) % MOD;

    cout << ans;
    return 0;
}