Modular Exponentiation

Given three integers a, b, and m, compute (a^b) mod m using fast (binary) exponentiation. Here b can be very large, so a naive loop that multiplies a by itself b times is too slow - your solution must run in O(log b) time.

Input: A single line containing three space-separated integers a, b, and m. Output: Print a single integer: (a^b) mod m.

0 <= a <= 10^9, 0 <= b <= 10^18, 2 <= m <= 10^9

Taking the modulus after EVERY multiplication (not just at the very end) is essential to keep intermediate values from overflowing - a subtle but critical implementation detail, since a and m being under 10^9 each means a single product still safely fits in a 64-bit type before the mod is applied.

Compute a large power of a number, taken modulo m, without ever multiplying the base by itself billions of times. Brute force: Multiply a by itself b times directly in a loop - this costs O(b), completely impractical when b can be up to 10^18. Optimised: Binary exponentiation exploits the fact that ANY exponent can be expressed as a sum of powers of 2 (its binary representation) - repeatedly squaring the base builds up a^1, a^2, a^4, a^8, ... in just O(log b) steps, and multiplying together only the ones corresponding to SET bits of b directly constructs a^b without ever looping b times.

1. Use BINARY EXPONENTIATION: repeatedly SQUARE the base and HALVE the exponent. 2. Whenever the current bit of the exponent is 1, multiply the running result by the current base. 3. Take the mod after EVERY multiplication, so intermediate values never grow unbounded.

Time: O(log b) - the number of squaring steps is proportional to the number of bits in the exponent. Space: O(1) - a few running variables (or O(log b) stack frames if implemented recursively).

b=0 yields 1 mod m regardless of a. a=0 with b>0 yields 0. Use 64-bit arithmetic throughout since b can be as large as 10^18.

Be ready to explain the binary-representation insight clearly - decomposing b into its bits and building up the answer via repeated squaring is the entire idea, and this exact technique appears everywhere in competitive programming and cryptography (like RSA).