Fast Power

Lab Python Intermediate 20 points

Write a recursive power(b, e) that uses b^e = (b^(e/2))² for even e. Print the result modulo 1,000,000,007.

Input

One line: b e.

Output

b^e mod 1000000007.

Example

Input

2 10

Output

Sample input available Sample output available

Editor

Python

Hints

Compute the half power once and square it.

For odd e multiply by b once more.

Solution explanation

Halving the exponent each time needs only about log₂(e) calls. Python's pow(b, e, MOD) does this.

Show solution

MOD = 1_000_000_007


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


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

Output

Answer