a-to-the-power-b

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

SAMPLE INPUT
3 2 9
1 2 3

SAMPLE OUTPUT
1

Explanation

Product of all the numbers is 6. 2^6 = 64 . 64 mod 9 is 1

Source: hackerearth | Difficulty: EASY


Solutions: