자연수 \(A\)를 \(B\)번 곱한 정수를 \(C\)로 나눈 나머지를 구하시오.

입력

첫째 줄에 세 자연수 \(A\), \(B\), \(C\)가 공백으로 구분되어 주어진다. (\(1 \le A, B, C \le 2,147,483,647\))

출력

\(A^B\)를 \(C\)로 나눈 나머지를 출력한다.

예제 입력 1

10 11 12

예제 출력 1

4