함수

음이 아닌 정수 집합을 $\mathbb{N}_0$이라 할 때, 다음과 같이 정의된 함수 $f \, : \, \mathbb{N}_0 \to \mathbb{N}_0$가 주어진다.

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

$f(n)$을 $m$으로 나눈 나머지를 구하시오.

첫째 줄에 정수 $n$이 주어진다.

둘째 줄에 $n + 1$개의 정수 $a_0, \, a_1, \, \cdots, \, a_n$이 주어진다.

셋째 줄에 정수 $m$이 주어진다.

$f(n)$을 $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$은 소수이다.
• 입력으로 주어지는 모든 값은 정수이다.

참고로 $9^{9^9}$의 정확한 값은 무려 $369 \, 693 \, 700$자리이다.