#include <fstream>
#include <bitset>
using namespace std;

#define mod 1000003

int N,M,p[100001],i,a;

bitset<100001> x;

ifstream f("grigo.in");
ofstream g("grigo.out");

int main ()
{
    f >> N >> M;
    for( i = 1; i <= M; i++)
        f >> a, x[a] = 1;

    for( i = 1; i <= N; i++)
        if( x[i] ) p[i] = (i==1) ? 1 : p[i-1];
        else p[i]=( (long long) p[i-1] * (i-1) ) % mod;

    g << p[N];
    return 0;
}