def power(a, b):
    print(f'power({a}, {b})')
    if b == 0:
        return 1
    if b % 2 == 0:  # b even
        p = power(a, b // 2)
        return p * p
    return a * power(a, b - 1)
    
    # return a ** b

# a^0 = 1
# a^5 = a * a * a * a * a = a * (a * a * a * a) = a * a^4
# a^6 = a * a * a * a * a * a = (a * a * a) * (a * a * a) =
#       (a * a * a) ** 2
# a ** (2*n) = (a ** n) ** 2

print(power(5, 1000))