시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 64 MB 181 64 40 44.944%

문제

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

그리고 \(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\) ≤ 109, 0 ≤ \(k\) ≤ 109)가 공백으로 구분되어 주어진다.

출력

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

예제 입력

2 3

예제 출력

1

힌트

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

출처

Contest > kriiicon > 제 1회 kriiICPC G번

  • 문제를 만든 사람: august14
  • 문제의 오타를 찾은 사람: citizen