거듭제곱 나머지
면접 대비시간 제한0.5초메모리 제한128 MB
A의 B거듭제곱을 C로 나눈 나머지를 빠른 거듭제곱 알고리즘으로 계산합니다.
문제
자연수 A, B, C가 주어진다. A^B를 C로 나눈 나머지를 구하시오. A^B의 값은 매우 커질 수 있으므로 효율적으로 나머지를 계산해야 한다.
입력
첫째 줄에 A, B, C가 공백으로 구분되어 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
A^B를 C로 나눈 나머지를 출력한다.