24059번 - Function 다국어

You are given a function $f \, : \, \mathbb{N}_0 \to \mathbb{N}_0$ defined as below. ($\mathbb{N}_0$ denotes the set of non-negative integers.)

• $f(0) = a_0$
• $f(i) = a_i^{f(i - 1)}$ ($i \ge 1$)

Find the value of $f(n)$ modulo $m$.

The first line contains a single integer $n$.

The second line contains $n + 1$ integers $a_0, \, a_1, \, \cdots, \, a_n$.

The third line contains a single integer $m$.

Print the value of $f(n)$ modulo $m$.

• $0 \le n \le 2$
• $1 \le a_i \le 2 \times 10^9$ ($0 \le i \le n$)
• $2 \le m < 2 \times 10^9$; $m$ is a prime number.
• All values in input are integers.

As a note, the exact value of $9^{9^9}$ has a whopping $369 \, 693 \, 700$ digits.