#include<algorithm>
#define MOD 1000003
using namespace std;
int n,m;
bool f[100001];
void solve(){
    int i,nr;
    long long unsigned prev,next;
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; ++i){
        scanf("%d",&nr);
        f[nr]=1;}
    for(i=2,prev=1; i<=n; prev=next,++i)
        if(f[i])
            next=prev;
        else
            next=((i-1)*prev)%MOD;
    printf("%lld",next%MOD);}
int main(){
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);
    solve();
    return 0;}