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
mport scala.io.StdIn.readLine

object Main {

  def pow(x:Long, y:Long, z:Long):Long = {

    def multi(m:Long, n:Long) = { ( (m%z) * (n%z) ) % z }

    def pow2(m:Long, n:Long, odd:Long, b:Long):Long = {
      n match {
        case 0 => 1
        case 1 => multi(m, odd)
        case _ =>
          lazy val t = if(n%2 == 1) multi(odd, b) else odd
          pow2(multi(m,m), n/2, t, multi(b,b))
      }
    }
    pow2(x, y, 1, x)
  }

  def main(args: Array[String]) = {
    val l = readLine().split(" ").map(_.toLong)
    val (m, n) = (l(0), l(1))
    println(pow(m,n,1000000007))
  }
}