#include <bits/stdc++.h>

using namespace std;
ifstream in("grigo.in");
ofstream out("grigo.out");
const int nmax=100000, mod=1000003;
int n, m, f[nmax+1];
int main()
{
    int x;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>x;
        f[x]++;
    }
    long long rez=1;
    for(int i=2; i<=n; i++)
    {
        if(f[i]==0)
        {
            rez=(rez*(i-1))%mod;
        }
    }
    out<<rez;
}