Exponentiation

Exponentiation is a basic mathematical operation that raises a base number to an exponent to obtain a result. In the expression $a^n$, $a$ is the base and $n$ is the exponent, meaning $a$ is multiplied by itself $n$ times. The result is called the $n$-th power of $a$. For example, $2^3=2 \times 2 \times 2=8$ and $5^2=5 \times 5=25$. In the first case, the base is $2$ and the exponent is $3$. In the second case, the base is $5$ and the exponent is $2$. Exponentiation is used in many areas, such as solving equations and cryptography.

In many cryptographic algorithms based on number theory, such as RSA (Rivest-Shamir-Adleman) and Diffie-Hellman, modular exponentiation is a basic operation. Modular exponentiation raises a base to an exponent and then takes the remainder modulo a modulus. It is computationally heavy, but it can be carried out fairly quickly even for very large numbers.

Let $x+\frac{1}{x}= \alpha$, where $\alpha$ is a positive integer. Write a program that computes $x^\beta + \frac{1}{x^\beta} \bmod m$ for given positive integers $\beta$ and $m$.

The input is one line with three space-separated positive integers $\alpha$, $\beta$, and $m$. Each of $\alpha$, $\beta$, and $m$ is less than $2^{64}$.

Output $x^\beta + \frac{1}{x^\beta} \bmod m$. You may assume that $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$.

$x$ can be a complex number. For example, if $\alpha=1$, then $x$ is either $\frac{1 + \sqrt{3}i}{2}$ or $\frac{1 - \sqrt{3}i}{2}$. However, $x^\beta + \frac{1}{x^\beta}$ is always an integer in this problem.