Ranjeet has recently learned how to calculate power of base x to y . Now people being jealous of him all sat together and framed a tough question to show that he has not learned anything. They gave him a base x and a list of numbers A. They asked him what would be the answer of x to the power product of all numbers in a list .
For example let x = 2 and list = {1,2,3} then you have to print 2^(1 x 2 x 3). Now for larger values there would be no way to type the long answer so they asked him to calculate the answer modulo M

NOTE : For all test files M will be always coprime to the base X

Input
First line contains N,x and M as input. Next line contains N space separated numbers

Constraints
1 ≤ N ≤ 10^6
1 ≤ M ≤ 10^9+7
1 ≤ x ≤ 10^9
1 ≤ A[i] ≤ 10^18