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.