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=10**9+7

m,n=map(int,input().split())
# def pow(m,n):
#     # mのn乗をmodを方にしてO(logn)で計算
#     if n==0:return 1
#     elif n%2==0:
#         return pow(m**2%mod,n//2)%mod
#     else:
#         return (pow(m**2%mod,n//2)*m)%mod

def pow(m,n,mod):
    rem=1
    while n>0:
        if n%2==1:
            rem=rem*m%mod
        m=m**2%mod
        n//=2
    return rem%mod

print(pow(m,n,mod))
