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

def power2(n):
  global ans
  if n == 1:
    tmp =  m % p
  elif n % 2 == 0:
    tmp = power2(n//2) ** 2 % p
  else:
    tmp =  power2(n//2) * power2((n+1)//2) % p
  return ans * tmp % p
    
m, n = map(int, input().split())
p = 10**9+7
ans = 1
print(power2(n))
