performs exponentiation similarly to the builtin pow or functions allows also for calculating the exponentiation modulo iterative version of binary exponentiation calculate a n if mod is specified return the result modulo mod time complexity ologn space complexity o1 recursive version of binary exponentiation calculate a n if mod is specified return the result modulo mod time complexity ologn space complexity ologn iterative version of binary exponentiation calculate a n if mod is specified return the result modulo mod time complexity o log n space complexity o 1 recursive version of binary exponentiation calculate a n if mod is specified return the result modulo mod time complexity o log n space complexity o log n
def power(a: int, n: int, mod: int = None):
    
    ans = 1
    while n:
        if n & 1:
            ans = ans * a
        a = a * a
        if mod:
            ans %= mod
            a %= mod
        n >>= 1
    return ans


def power_recur(a: int, n: int, mod: int = None):
    
    if n == 0:
        ans = 1
    elif n == 1:
        ans = a
    else:
        ans = power_recur(a, n // 2, mod)
        ans = ans * ans
        if n % 2:
            ans = ans * a
    if mod:
        ans %= mod
    return ans