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
import math
a=1000000007

m,n=[int(i) for i in input().split(" ")]

pow_list=[m]
x=int(math.log2(n))
for i in range(x+1):
    pow_list.append((pow_list[-1]**2)%a)

result=1
for i in range(x+1):
    if n>=2**(x-i):
        n-=2**(x-i)
        result=(result*pow_list[x-i])%a

print (result)