#include <stdio.h>

int M, N, cnt = 1;
char viz[100005];

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

    scanf("%d %d", &N, &M);
    
    for (; M; --M)
    {
        scanf("%d", &i);
        viz[i] = 1;
    }

    for (i = 1; i <= N; ++i)
        if (!viz[i])
            cnt = ((long long)cnt * (i-1)) % 1000003;

    printf("%d\n", cnt);

    return 0;
}