#include <fstream>
#define mod 1000003
using namespace std;
ifstream fin("grigo.in");
ofstream fout("grigo.out");
long long n,m,a[100005];
int main()
{
    long long i,x,sol; sol=1;
    fin>>n>>m;
    for(i=1;i<=m;++i)
    { fin>>x;
        a[x]=1;
    }
    for(i=1;i<=n;++i)
        if(a[i]==0)
         sol=(sol*(i-1))%mod;
    fout<<sol;
    return 0;
}