#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) 
	{
		d[i]=0;
		if (max<a[i]) { max=a[i]; continue; }
		d[i]=1;
	}

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

	for (i=1; i<=m; ++i) d[c[i]]=3;
	for (i=1; i<=n; ++i) 
	{
		if (d[i]==3) continue;
		if (d[i]==0) 
		{
			q=0; 
			break;
		}
	}
	if (q==1)
	{
		q=1;
	}
	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;
}