Ben is playing around with some tower blocks!

Each of his $N$ tower blocks are labelled with an integer, $a_i$. He stacks them vertically, with $a_1$ at the bottom and $a_N$ at the top.

Ben built his tower and is very proud of it, but is now wondering how powerful it is. As everyone knows, a single tower block's power is equal to its label.

However, in a tower consisting of multiple blocks, the power grows very quickly. In a tower of $N$ blocks, the power is equal to $a_1^{\left(a_2^{(a_3^{\cdots })}\right)}$. Formally, if $P(a_1,a_2,\dots ,a_N)$ is the power of a tower consisting of $N$ blocks with labels $a_i$, then $P(a_1,a_2,\dots ,a_N)=a_1^{P(a_2,a_3,\dots ,a_N)}$, with $P(a_N)=a_N$.

Ben really wants to know the power of his tower. However, knowing his number might be way too big, he will be happy if you can tell him the power modulo $M$. Can you help him?

Constraints

$1\le N\le {10}^6$

$2\le M\le {10}^9$

$1\le a_i\le {10}^9$

Subtask 1 [1/15]

$1\le N\le 3$

$M$ is prime.

Subtask 2 [14/15]

No additional constraints.

Input Specification

The first line will contain $N$, the number of blocks in Ben's tower, and $M$, the modulus.

The next line will contain $N$ integers, the labels on Ben's blocks, from $a_1$ to $a_N$.

Output Specification

Output the power of Ben's tower, mod $M$.

Sample Input 1

3 5
2 3 2

Sample Output 1

2

Explanation for Sample Output 1

The power of Ben's tower is $2^{(3^2)}\equiv 2^9\equiv 512\equiv 2(\mathrm{mod}5)$.

Note that you do not need to get the correct output on this case to pass the first subtask.

Sample Input 2

3 17
3 5 7

Sample Output 2

12

Sample Input 3

12 35929738
62525611 69201951 54844075 40933790 64603110 102648769 67604167 54424854 69048209 51968609 55767140 95916210

Sample Output 3

9996111