#include <fstream>
 
using namespace std;
 
const char InFile[]="grigo.in";
const char OutFile[]="grigo.out";
const int MaxN=100111;
const int MOD=1000003;
 
ifstream fin(InFile);
ofstream fout(OutFile);
 
int N,M,sol;
char _fixed[MaxN];
 
int main()
{
    fin>>N>>M;
    for(register int i=1;i<=M;++i)
    {
        fin>>sol;
        _fixed[sol]=1;
    }
    fin.close();
     
    if(!_fixed[1])
    {
        sol=0;
    }
    else
    {
        sol=1;
        for(register int i=2;i<=N;++i)
        {
            if(!_fixed[i])
            {
                sol=(1LL*sol*(i-1))%MOD;
            }
        }
    }
     
    fout<<sol;
    fout.close();
    return 0;
}