using namespace std;
#include<cstdio>
const int MAX_N = 100007;
#define mod 1000003
int uz[MAX_N];
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 <= M; ++i)
	{
		scanf("%d", &x); 
		uz[x] = 1;
	}
	for(i = 1; i <= N; ++i)
		if( !uz[i] ) sol = (1LL*sol * ( i - 1 )) % mod;
	printf("%d\n",sol);
}