A relay handshake derives its session key by raising a base value to a large exponent and keeping only the remainder modulo m. Because the exponent can be huge, multiplying the base one time at a time is far too slow; the intended approach squares the running base and consumes the exponent bit by bit.
Given non-negative integers base and exp and a positive integer m, compute base raised to the power exp, taken modulo m. Adopt the usual convention that any value raised to the power 0 equals 1 (so the answer when exp is 0 is 1 mod m).
A single line with three integers: base exp m.
A single integer: base to the power exp, modulo m.
Example 1
Input
2 10 1000
Expected
24
Explanation
2 to the 10th power is 1024, and 1024 mod 1000 is 24.
Example 2
Input
3 0 7
Expected
1
Explanation
Any value to the power 0 is 1, and 1 mod 7 is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →