세 자연수 A, B, C가 주어진다.

우리는 A를 정확히 B번 곱한 값을 생각할 수 있다.

즉, 다음과 같은 값을 구하려는 것이다.

A × A × A × ... × A

위 식에서 A는 총 B번 등장한다.

하지만 A와 B의 값이 커질 수 있기 때문에, 이 값을 그대로 계산하면 결과가 매우 커질 수 있다.

따라서 실제 값을 모두 구하는 대신, 이 값을 C로 나누었을 때의 나머지만 구하려고 한다.

즉, A를 B번 곱한 수를 C로 나눈 나머지를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다.

A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1

10 11 12

예제 출력 1

4