using namespace std;
#include<cstdio>
const int MAX_N = 100007;
#define mod 1000003
int main()
{
	int N, M,i,j, sol = 1, p = 1;
	freopen("grigo.in","r",stdin); freopen("grigo.out","w",stdout);
	scanf("%d%d%d",&N,&M, &j);
	for(i = 1; i <= N; ++i)
	{
		if( i == j )
		{
			if(p < M) scanf("%d",&j), ++p;
		}
		else sol = (1LL*sol * ( i - 1 )) % mod;
	}    
	printf("%d\n",sol);
}