#include<fstream>
using namespace std;
ifstream in("grigo.in");
ofstream out("grigo.out");
int i,n,m,x;
long long p;
bool v[100001];
int main(){
    in >> n >> m;
    for( i = 1; i <= m; i ++ ){
        in >> x;
        v[x] = 1;
    }
    p = 1;
    for( i = 1; i <= n; i ++ ){
        if( v[i] == 0 ){
            p*= i-1;
            p=p%1000003;
        }
    }
    out<<p;
    return 0;
}