Hide

Problem B
Square and Multiply

Languages en is

Implement a memory efficient version of the square and multiply algorithm.

Input

Input is three lines. The first line contains the integer $g$. The second line contains the integer $A$. The third line contains the integer $N$. It is guaranteed that $1 \leq g, N \leq 10^9$ and $0 \leq A \leq 10^{18}$.

Output

Output one line with the integer $g^{A} \pmod{N}$.

Sample Input 1 Sample Output 1
3
53
356
75

Please log in to submit a solution to this problem

Log in