#include <stdio.h>
#define MOD 1000003
#define NMAX 100100

bool visible[NMAX];

int main()
{
    int i, x, N, K, sol = 1;

    freopen("grigo.in", "r", stdin); //grigo = wefgef?!
    freopen("grigo.out", "w", stdout);

    scanf("%d%d", &N, &K);
    for (i = 1; i <= K; i ++)
    {
        scanf("%d", &x);
        visible[x] = 1;
    }

    for (i = 1; i <= N; i ++)
        if (!visible[i])
            sol = (long long)sol * (i - 1) % MOD;

    printf("%d", sol);
    return 0;
}