Modular Exponentiation

Compute (base^exp) mod mod efficiently.

Function signature

func ModPow(base int64, exp int64, mod int64) int64

Example

base = 2, exp = 10, mod = 1000
output = 24

Constraints

• 0 <= base <= 1_000_000_000_000
• 0 <= exp <= 1_000_000_000_000_000_000
• 1 <= mod <= 1_000_000_007

Notes

• Use binary exponentiation in O(log exp).