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

object Main {
  val N = 1000000007

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

  def pow(m: => Long, n: => Long, b1: => Long, b2: => Long, b3: => Long):Long = {
    n match {
      case 0 => 1
      case 1 => multi(b1,b3)
      case _ =>
        val c = b2 match {
          case 1 => m % N
          case _ => multi(b2,b2)
        }
        pow(m, n/2, multi(b1,b1), c, (if (n%2==0) 1 else c) * (b3 % N))
    }
  }

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