#include <fstream>
#include <bitset>
#define X 1000003
#define Nmax 100099
using namespace std;
ifstream f("grigo.in");
ofstream g("grigo.out");

int n,m;
unsigned long long sol;
bitset < Nmax > p;

int main()
{
    f>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int nr;
        f>>nr;
        p[nr]=1;
    }
    sol=1;
    for (int i=1;i<=n;i++)
        if (!p[i]) sol=( sol*(i-1) )% X;
    g<<sol<<'\n';
    return 0;
}