A power tower of k positive integers a_1, a_2, ..., a_k is evaluated right-to-left: a_1 ^ (a_2 ^ ( ... ^ (a_{k-1} ^ a_k) ... )). This value can be astronomically large even for small k, so you must compute it modulo m without ever materializing the full tower.
Given the tower's k values and a modulus m, output the tower's value modulo m. You will need the generalized Euler's theorem (a^x = a^(x mod phi(m) + phi(m)) (mod m) whenever x >= phi(m), valid for any base a) to correctly reduce the exponent chain.
Input format
Line 1: a single integer k, the number of values in the tower.
Line 2: k space-separated integers a_1 .. a_k (the tower, outermost base first).
Line 3: a single integer m, the modulus.
Output format
A single integer: the value of the power tower a_1^(a_2^(...^a_k)), modulo m.
Constraints
- 1 <= k <= 3
- 1 <= a_i <= 6
- 1 <= m <= 1000000000