For a cryptography side-example, Oindrila needs fast modular exponentiation: base raised to a huge exponent, modulo a given number. Read base B, exponent E, and modulus M. Print B^E mod M using fast exponentiation (O(log E)), not a loop of E multiplications.
Input
Three integers B E M.
Output
B^E mod M.
Constraints
0 ≤ B ≤ 10^9, 0 ≤ E ≤ 10^18, 1 ≤ M ≤ 10^9
Sample Input
2 10 1000
Sample Output
24
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.