Exponial

큰 수를 만드는 방법은 여러 가지가 있다. 예를 들면 다음과 같다.

• 거듭제곱: $42^{2016} = \underbrace{42 \times 42 \times \cdots \times 42}_{2016 \text{개}}$
• 팩토리얼: $2016! = 2016 \times 2015 \times \cdots \times 2 \times 1$

이 문제에서는 두 연산을 섞은 exponial을 다룬다. exponial은 모든 양의 정수 $n$에 대해 다음과 같이 정의된다.

$\mathrm{exponial}(n) = n^{(n-1)^{(n-2)^{\cdots^{2^1}}}}$

예를 들어 $\mathrm{exponial}(1) = 1$이고, $\mathrm{exponial}(5) = 5^{4^{3^{2^1}}} \approx 6.206 \times 10^{183230}$이다. 거듭제곱은 오른쪽부터 계산한다. 즉 $a^{b^c} = a^{(b^c)}$이다.

exponial은 값이 너무 커서 그대로 다루기 어렵다. $\mathrm{exponial}(n)$을 $m$으로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $n$과 $m$이 공백을 사이에 두고 주어진다. ($1 \le n \le 10^9$, $1 \le m \le 10^9$)

첫째 줄에 $\mathrm{exponial}(n)$을 $m$으로 나눈 나머지를 출력한다.