#include <stdio.h>
#include <stdlib.h>

int n,m;
int* v;
int * perm;
int k;
int nr_sol;
void read ()
{
	int i;
	FILE* f=fopen("grigo.in","r");
	fscanf(f,"%d%d",&n,&m);
	v=(int*)calloc(m,sizeof(int));
	perm=(int*)calloc(n+1,sizeof(int));
	nr_sol=0;
	for(i=0;i<m;i++)
		fscanf(f,"%d",&v[i]);
	fclose(f);
}

void init()
{
	perm[k]=0;
}

int is(int pos)
{
	int i;
	for(i=0;i<m;i++)
		if (v[i]==pos)
			return 1;
	return 0;
}

int valid ()
{
	int i,j;
	for(i=1;i<k;i++)
		{
			if (perm[i]==perm[k])
				return 0;
		}
	for (i=0;i<m;i++)
		for (j=1;j<v[i] && v[i]<=k;j++)
			if (perm[v[i]]<perm[j])
				return 0;
	for (i=1;i<=k;i++)
		if (!is(i))
			{
				int z;
				int ok=0;
				for (z=1;z<i;z++)
					{
						if (perm[z]>perm[i])
							ok=1;
					}
				if (!ok)
					return 0;
			}
	return 1;
}

int succ()
{
	if (perm[k]<n)
		{
			perm[k]++;
			return 1;
		}
		else 
			return 0;
}

int solution()
{
	if (k==n)
		return 1;
	return 0;
}

void count()
{
	nr_sol++;
}

void back()
{
	k=1;
	int ok;
	init();
	while(k>0)
		{
			do{}while ((ok=succ())&& !valid());
			if (ok)
				{
					if (solution())
						count();
						else
							{	
								k++;
								init();
							}
				}
				else
					k--;
		}
}

int main()
{
	read();
	back ();
	FILE* g=fopen("grigo.out","w");
	fprintf(g,"%d",nr_sol%1000003);
	fclose(g);
	getchar();
	return 0;
}