using namespace std;
#include<cstdio>
const int MAX_N = 100000;
const long long mod = 1000003;
int main()
{
	int N, M,i,j = 1, 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 && p < M) scanf("%d",&j), ++p;
		else sol = (1LL*sol * ( i - 1 )) % mod;
	}
	printf("%d\n",sol);
}