(a)의 거듭제곱 (a^{b})를 편하게 (pow_{a}(b))라고 나타내어 보자.</p>

그리고 (pow_{a}^{0}(a) = a, pow_{a}^{k+1}(a) = pow_{a} (pow_{a}^{k}(a)) (k \ge 0))라고 하자.

우리의 일은 (a)와 (k)가 주어질 때 (pow_{a}^{k}(a))를 계산하는 것이다. 즉

(a^{a^{a^{a^{a^{...^{{...}^{{a}^{a}}}}}}}}) ((a)가 (k+1)개)

을 계산하는 것이다. 주의해야 할 점은 만약 (k = 2)이라고 할 때

((a^{a})^{a} \neq a^{(a^{a})})

라는 것이다. 우리가 구하는 것은 후자이다.

입력 형식

첫 번째 줄에 (a)와 (k) (1 ≤ (a) ≤ 10⁹, 0 ≤ (k) ≤ 10⁹)가 공백으로 구분되어 주어진다.

출력 형식

(pow_{a}^{k}(a))의 값을 출력한다. 답이 매우 커질 수 있으므로 답을 (a+1)로 나눈 나머지를 출력한다.

예제 입력

2 3

예제 출력

1

힌트

(pow_{2}^{3}(2) = 2^{2^{2^{2}}} = 65,536)이므로, 이를 3으로 나눈 나머지인 1을 출력한다.