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
#B
import math
mod = 10**9+7
m,n = map(int,input().split()) #m^n % mod
n2 = math.ceil(math.sqrt(n))

b = bin(n)
b = b.lstrip("0b")
blist = list(b)
blist = blist[::-1]
ans = 1
beki = [m]
for i in range(n2):
    m = (m**2)%mod
    beki.append(m)

blen = len(blist)
ans = 1
for i in range(blen):
    if blist[i] == "1":
        ans*=beki[i]
        ans%=mod
        
print(ans)

