#include<stdio.h>
#define MOD 1000003


long long u[100004], i, n, k, x, y;

int main(){
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);

    scanf("%lld %lld",&n, &k);
    for (; k; k--){
        scanf("%d",&i);
        u[i] = 1;
    }

    for (i = 2, x = 1; i <= n; x = y, i++)
        y = (u[i] ? x : ((i-1)* x) % MOD);

    printf("%lld\n", y);
    return 0;
}