#include <stdio.h>
#include <stdlib.h>
#define MOD 1000003
int main()
{
    int i,n,m,rez,x;
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);
    scanf("%d%d",&n,&m);
    rez=1;
    for(i=1; i<=n-m; i++)
        rez=((long long)rez*i)%MOD;
    scanf("%d",&x);
    for(i=2; i<=m; i++)
    {
        scanf("%d",&x);
        rez=((long long)rez*(n+1-x))%MOD;
    }
    printf("%d\n",rez);

    return 0;
}