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
object Main {
	
	// 繰り返し二乗法　O(log n)
	def pow(x: Int, n: Int, m: Int): Int = n match{
		case 0 => 1
		case n if n%2==0 => pow(x*x, n/2, m) % m
		case n if n%2!=0 => pow(x*x, n/2, m) * x % m
	}
	
	def main(args: Array[String]) = {
		val sc = new java.util.Scanner(System.in)
		val m,n = sc.nextInt
		
		println(pow(m,n,1000000007))
	}

}