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).
Input format
A single line with three integers: base exp m.
Output format
A single integer: base to the power exp, modulo m.
Constraints
- 0 <= base <= 1000000000
- 0 <= exp <= 1000000000
- 1 <= m <= 1000000000