
# O(log n) time | space
def myPow(x,n):
    if n < 0:
        x = 1/x
        n = -n
    return fastPow(x, n)

def fastPow( base, power):
    if power == 0:
        return 1
    half = fastPow(base, power//2)
    if power % 2 == 0:
        return half * half
    else:
        return half * half * base

2d41245a1c0376e896b7b9f6287860eebf05b73d
<mask token>

def myPow(x, n):
    if n < 0:
        x = 1 / x
        n = -n
    return fastPow(x, n)


<mask token>

def myPow(x, n):
    if n < 0:
        x = 1 / x
        n = -n
    return fastPow(x, n)


def fastPow(base, power):
    if power == 0:
        return 1
    half = fastPow(base, power // 2)
    if power % 2 == 0:
        return half * half
    else:
        return half * half * base


# O(log n) time | space
def myPow(x,n):
    if n < 0:
        x = 1/x
        n = -n
    return fastPow(x, n)

def fastPow( base, power):
    if power == 0:
        return 1
    half = fastPow(base, power//2)
    if power % 2 == 0:
        return half * half
    else:
        return half * half * base
