#include <cstdio>

#define FIN "grigo.in"
#define FOUT "grigo.out"

#define MOD 1000003
#define MAXN 100001

int N, M;
int P[MAXN], R[MAXN];

int main()
{
    int i, x;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d %d", &N, &M);

    for (i = 1; i <= M; ++ i)
    {
        scanf("%d", &x);

        P[x] = 1;
    }

    for (i = 1, R[0] = 1; i <= N; ++ i)
        R[i] = P[i] ? R[i - 1] : (1LL * R[i - 1]  * (i - 1)) % MOD;

    printf("%d\n", R[N]);
}