For given integers m and n, compute mn (mod 1,000,000,007). Here, A (mod M) is the remainder when A is divided by M.

Constraints

* 1 ≤ m ≤ 100
* 1 ≤ n ≤ 109

Input


m n


Two integers m and n are given in a line.

Output

Print mn (mod 1,000,000,007) in a line.

Examples

Input

2 3


Output

8


Input

5 8


Output

390625
mod = 1000000007

def binary(n):
    if n == 0:
        return [0]
    else:
        b = []
        while n > 0:
            b = [n%2] + b
            n = n//2
        return b

def power(m,n):
    nbi = binary(n)
    l = len(nbi)
    s = 1
    for i in range(0,l):
        if nbi[l-i-1] != 0:
            p = m
            for j in range(0,i):
                p = (p*p) %mod
            s = s * p
            s = s %mod
    return s

M,N = map(int,input().strip().split(" "))
print(power(M,N))

