#include<stdio.h>
int main()
{
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);
	int i,n,m,p;
	char v[100005];
	long long prod;
    scanf("%d%d",&n,&m);
	prod=1;
	for (i=1;i<=m;i++)
	{
		scanf("%d",&p);
		v[p]=1;
	}
    for (i=1;i<=n;i++)
    {
        if(!v[i])
            prod*=(i-1);
        prod%=1000003;
    }
    printf("%lld",prod);
}