#include<stdio.h>
char v[101010];
int N,rez=1,M,x;
int main()
{
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);
    scanf("%d%d",&N,&M);
        for(int i=1;i<=M;++i)
        {
            scanf("%d",&x);
            v[x]=1;
        }
    for(int i=1;i<=N;++i)
    {
        if(!v[i])
            rez=rez*(i-1);
        rez%=1000003;
    }
    printf("%d",rez);
}