거듭제곱 (빠른 거듭제곱)

A^B mod C를 구하라. B가 최대 10^18이므로 분할 정복을 쓴 빠른 거듭제곱으로 O(log B)에 구현하라.

B가 짝수이면 A^B = (A^(B/2))^2, 홀수이면 A^B = A × A^(B-1)로 재귀한다. 중간 곱셈마다 mod C를 취한다.

입력

첫째 줄에 A, B, C가 공백으로 구분되어 주어진다. (1 ≤ A, C ≤ 10^9, 1 ≤ B ≤ 10^18)

출력

A^B mod C를 출력하라.

예제 입력 1

10 11 12

예제 출력 1

4