Challenge: Fast Power

Lab Python Beginner 10 points

Read a and b and print a^b using a recursive function that halves b each time (don't use ** or pow).

Input

Two whole numbers a b (0 ≤ b ≤ 200).

Output

a to the power b.

Example

Input

2 10

Output

Sample input available Sample output available

Editor

Python

Hints

Base case: b == 0 gives 1.

Work out half = power(a, b // 2) once, then square it.

If b is odd, multiply by a once more.

Solution explanation

b halves on every call, so there are only about log₂(b) calls.

Show solution

def power(a, b):
    if b == 0:
        return 1
    half = power(a, b // 2)
    if b % 2 == 0:
        return half * half
    return half * half * a

a, b = map(int, input().split())
print(power(a, b))

Output

Answer