471. Power Function (Exponentiation by Squaring)

Given integers base and exp (exp >= 0), compute base^exp modulo 10^9+7. Use fast exponentiation (binary exponentiation) to solve in O(log exp).

Input: Integers base (0 <= base <= 10^9) and exp (0 <= exp <= 10^9).

Output: base^exp mod (10^9 + 7).

Examples

Example 1

Input: 2, 10
Output: 1024
Explanation: 2^10 = 1024. 1024 mod (10^9+7) = 1024.

Example 2

Input: 3, 5
Output: 243
Explanation: 3^5 = 243.

Example 3

Input: 2, 0
Output: 1
Explanation: Any number to the power 0 is 1.