#include <stdio.h>

int n,m,i,j,a[10000],b[10000],c[10000],d[10000],sol;

int verif()
{
	int max=0;
	for (i=1; i<=n; ++i) 
	{
		if (max<a[i]) { max=a[i]; continue; }
		d[i]=1;
	}
	int q=1;
	for (i=1; i<=m; ++i) if (d[c[i]]) { q=0; break; };
	return q;
}

void back(int x)   
{   
    if (x>n)   
    {   
		if (verif()) ++sol;
		sol=sol%1000003;
        return;   
    }   
    int i;   
    for (i=1; i<=n; ++i)   
    {   
        if (b[i]==1) continue;   
        a[x]=i;   
        b[i]=1;   
        back(x+1);   
        b[i]=0;   
    }   
}   

int main()
{
	freopen("grigo.in","r",stdin);
	freopen("grigo.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1; i<=m; ++i) scanf("%d",&c[i]);
	back(1);
	printf("%d\n",sol);
	return 0;
}