Modular Exponentiation
MediumMathBit Manipulation
Description
Compute (a raised to the power b) modulo m. Use fast (binary) exponentiation. Inputs are non-negative integers, m ≥ 1.
Examples
Input:
a = 2, b = 10, m = 1000Output:
24Explanation:
2^10 = 1024, and 1024 mod 1000 equals 24.
Input:
a = 5, b = 0, m = 7Output:
1Explanation:
Any nonzero base to the power 0 is 1, and 1 mod 7 equals 1.
Input:
a = 3, b = 100, m = 1000000007Output:
886041711Explanation:
3^100 mod 1000000007 equals 886041711 by fast exponentiation.
Constraints
- •
0 ≤ a ≤ 10⁹ - •
0 ≤ b ≤ 10¹⁸ - •
1 ≤ m ≤ 10⁹