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 |
