693. Power of a Number (x^n)

Given a base integer x and a non-negative exponent n, compute x^n using recursion. Implement the fast recursive power (binary exponentiation) for full credit: x^n = (x^(n/2))^2 if n is even, and x × x^(n-1) if n is odd. Return the exact integer value.

Input: Two integers x and n, separated by a comma. x is any integer (-1000 ≤ x ≤ 1000), n is a non-negative integer (0 ≤ n ≤ 62).

Output: A single integer — x raised to the power n.

Examples

Input: 2, 10
Output: 1024
Explanation: 2^10=1024. Fast power: 2^10=(2^5)^2=(2×2^4)^2=(2×(2^2)^2)^2 = 1024.

Input: 5, 0
Output: 1
Explanation: Any number to the power 0 is 1 (base case).

Input: 3, 5
Output: 243
Explanation: 3^5=3×3^4=3×81=243.

Constraints

• -1000 <= x <= 1000
• 0 <= n <= 1000 (results kept within the 64-bit safe range)

Asked by