ll@n;
ull@m,@b,z=1;
m%=b;
ull p=EulerPhi(b);
rep(i,n){
	ull@a;
	z=z*(powmod(m,(a-1)%p+1,b)+1)%b;
}
wt(z);