#include<iostream>
#include<fstream.h>

using namespace std;

ifstream fin("grigo.in");
ofstream fout("grigo.out");

void citirea();

int n,m,x,a[100000];
long long rez;

void citirea(){
    fin>>n>>m;//cout<<n<<" "<<m<<endl;
    for(int i=0;i<m;i++){
        fin>>x;//cout<<x<<" ";
        a[x]=1;
    }
}

int p(int s){
    //cout<<s<<" ";
    if (s==1) return 1;
    else return s*p(s-1);
}

int main(){

    citirea();

    //cout<<endl;

    if (m==2) rez=p(n-1);
    if (m==n) rez=1;
    if (m==1) rez=1;

    rez=rez%1000003;
    fout<<rez;

    fin.close();
    fout.close();
    return 0;
}