Implement Power Function

Create myPow(x, n) to return the value of the floating-point base x raised to the integer exponent n. Because n may be below zero, the implementation must correctly produce reciprocal powers. Your algorithm must run in O(log n) time.

Input:

• A floating-point value x between [-100.0, 100.0]
• An integer value n between [-2^31, 2^31 - 1]

Output:

• A floating-point result equal to x raised to the power n.

Example:

Input: x = 3.0, n = 4
Output: 81.0

Input: x = 1.5, n = 3
Output: 3.375

Input: x = 4.0, n = -2
Output: 0.0625

The first result is $3.0 \times 3.0 \times 3.0 \times 3.0$; the final result is the reciprocal of $4.0^{2}$.

Example

Input: x = 5.0, n = 3

Output:
125.0