1356. Compute Power x^n Using Bits (Fast Exponent)

Given a non-negative base x and a non-negative exponent n, compute x raised to the power n modulo 1000000007 using binary exponentiation, where the exponent's bits decide which squared powers to multiply together.

Input: A JSON object {"x": <base>, "n": <exponent>}.

Output: Return x^n modulo 1000000007.

Examples

Input: {"x":2,"n":10}
Output: 1024
Explanation: 2^10 = 1024, which is already below the modulus.

Input: {"x":5,"n":0}
Output: 1
Explanation: Any base to the power 0 is 1.

Constraints

• 0 <= x <= 10^9
• 0 <= n <= 10^18

Asked by