거듭제곱

지수 연산은 밑(base)을 지수(exponent)만큼 거듭해서 곱하는 기본적인 수학 연산이다. $a^n$에서 $a$는 밑, $n$은 지수이며, $a$를 $n$번 곱한다는 뜻이다. 이 결과를 $a$의 $n$제곱이라고 부른다. 예를 들어 $2^3=2 \times 2 \times 2=8$이고 $5^2=5 \times 5=25$이다. 첫 번째 예에서 밑은 $2$, 지수는 $3$이고, 두 번째 예에서 밑은 $5$, 지수는 $2$이다. 지수 연산은 방정식을 풀거나 암호학 등 여러 분야에서 쓰인다.

RSA(Rivest-Shamir-Adleman)와 Diffie-Hellman처럼 정수론에 기반한 많은 암호 알고리즘에서는 모듈러 지수 연산이 기본 연산이다. 모듈러 지수 연산은 밑을 지수만큼 거듭제곱한 값을 모듈러스로 나눈 나머지를 구한다. 계산량은 많지만, 매우 큰 수에서도 비교적 쉽게 수행할 수 있다.

$x+\frac{1}{x}= \alpha$이며 $\alpha$는 양의 정수이다. 주어진 양의 정수 $\beta$와 $m$에 대해 $x^\beta + \frac{1}{x^\beta} \bmod m$을 계산하는 프로그램을 작성하라.

입력은 한 줄이며, 공백으로 구분된 양의 정수 $\alpha$, $\beta$, $m$이 주어진다. $\alpha$, $\beta$, $m$은 모두 $2^{64}$보다 작다.

$x^\beta + \frac{1}{x^\beta} \bmod m$을 출력한다. $x^\beta + \frac{1}{x^\beta}$는 정수라고 가정해도 된다. 답이 여러 개이면 $0$부터 $m-1$ 범위의 값 중 어느 것을 출력해도 된다.

$x$는 복소수일 수 있다. 예를 들어 $\alpha=1$이면 $x$는 $\frac{1 + \sqrt{3}i}{2}$ 또는 $\frac{1 - \sqrt{3}i}{2}$이다. 하지만 이 문제에서 $x^\beta + \frac{1}{x^\beta}$는 항상 정수이다.