#GYM104619E. Exponentiation
Exponentiation
Description
Exponentiation is a mathematical operation that involves raising a base number to a certain exponent to obtain a result. In the expression $a^n$, where $a$ is the base and $n$ is the exponent, it means multiplying $a$ by itself $n$ times. The result of this operation is called the exponentiation of $a$ to the $n$-th power. For examples, $2^3 = 2 \times 2 \times 2 = 8$ and $5^2 = 5 \times 5 = 25$. In these examples, $2$ is the base, $3$ is the exponent in the first case, and $5$ is the base, and $2$ is the exponent in the second case. Exponentiation is a fundamental operation in mathematics and is commonly used in various contexts, such as solving equations, and cryptography.
In many cryptographic algorithms, particularly those based on number theory like RSA (Rivest-Shamir-Adleman) and Diffie-Hellman, modular exponentiation is a fundamental operation. Modular exponentiation involves raising a base to an exponent modulo a modulus. This operation is computationally intensive but relatively easy to perform, even for very large numbers.
Let $x+\frac{1}{x}=\alpha$ where $\alpha$ is a positive integer. Please write a program to compute $x^{\beta}+\frac{1}{x^{\beta}}~\mbox{mod}~m$ for given positive integers $\beta$ and $m$.
The input has only one line, and it contains three space-separated positive integers $\alpha$, $\beta$ and $m$. $\alpha$, $\beta$ and $m$ are positive integers less than $2^{64}$.
Outout $x^{\beta}+\frac{1}{x^{\beta}}~\mbox{mod}~m$. You may assume $x^{\beta}+\frac{1}{x^{\beta}}$ is an integer. If there are multiple solutions, you may output any of them in the range from $0$ to $m-1$.
Input
The input has only one line, and it contains three space-separated positive integers $\alpha$, $\beta$ and $m$. $\alpha$, $\beta$ and $m$ are positive integers less than $2^{64}$.
Output
Outout $x^{\beta}+\frac{1}{x^{\beta}}~\mbox{mod}~m$. You may assume $x^{\beta}+\frac{1}{x^{\beta}}$ is an integer. If there are multiple solutions, you may output any of them in the range from $0$ to $m-1$.
1 2 3
5 4 321
3 3 333
8 8 888
2
206
18
626
Note
$x$ can be a complex number. For example, $x$ is either $\frac{1+\sqrt{3}i}{2}$ or $\frac{1-\sqrt{3}i}{2}$ if $\alpha=1$. However, $x^{\beta}+\frac{1}{x^\beta}$ is always an integer in this problem.