#include<stdio.h>
#define MOD 1000003


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

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

    scanf("%d %d",&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", x);
    return 0;
}