#include <stdio.h>
#include <bitset>

using namespace std;

long n,m,i,p,sol;
bitset <100005>v;

int main(){
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);
    
    scanf("%ld %ld",&n,&m);
    for (i=1;i<=m;i++){
        scanf("%ld",&p);
        v[p]=1;
    }
    sol=1;
    for (i=1;i<=n;i++)
        if (!v[i])sol=(sol*(i-1))%1000003;
    printf("%ld\n",sol);
return 0;
}