Math Number Theory Bit Manipulation
Intermediate Level

Implement the fastPowerModulo method that calculates base raised to exponent under a given modulo efficiently.

The input contains three integers: base, exponent, and mod. Your task is to calculate base raised to exponent, then return the result after applying modulo mod.

For example, 2^5 = 32, and 32 % 13 = 6, so the answer is 6.

Example 1
Input:
base (int) = 2
exponent (int) = 5
mod (int) = 13
Return:
(int) 6
Example 2
Input:
base (int) = 3
exponent (int) = 4
mod (int) = 5
Return:
(int) 1
Example 3
Input:
base (int) = 10
exponent (int) = 0
mod (int) = 7
Return:
(int) 1

Use fast exponentiation so the power can be calculated without multiplying the base exponent times.

Keep a result value starting at 1. While the exponent is greater than 0, if the exponent is odd, multiply the result by the current base and take modulo. Then square the base, take modulo again, and divide the exponent by 2.

Pseudocode:

function fastPowerModulo(base, exponent, mod):
    result = 1
    base = base % mod
    while exponent > 0:
        if exponent is odd:
            result = (result * base) % mod
        base = (base * base) % mod
        exponent = exponent / 2
    return result
Run your code to see the result.