#include <bits/stdc++.h>
using namespace std;
ifstream fin("grigo.in");
ofstream fout("grigo.out");
const int NMAX = 100000;
const int MOD = 1000003;
int main(){
    int n, m, cnt, poz[NMAX];
    long long rez = 1;
    fin>>n>>m;
    for(int i=1; i<=m; i++){
        int val;
        fin>>val;
        poz[val]=val;
    }

    for(int i=1; i<=n; i++){
        if(!poz[i]){
            rez=(1LL*rez*(i-1))%MOD;
        }
    }
    fout<<rez;
}