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} (\mod N)$ .

Sample Input 1	Sample Output 1
3 53 356	75

Hide

Please log in to submit a solution to this problem

CPU Time limit1 second

Memory limit1024 MB

DifficultyNot Available

LinksStatistics

DownloadsSample data files

Source & LicenseArnar Bjarni ArnarsonT-513-Cryptography and Number Theory

You haven't made any submissions on this problem yet.

Editor:

Problem BSquare and Multiply

Input

Output

Problem B
Square and Multiply