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
let pow x y z =
  let mult x1 y1 = ((x1 mod z)*(y1 mod z)) mod z in
  let rec f m n b = match n with
      0 -> 1
    | 1 -> mult m b
    | _ -> f (mult m m) (n/2) (mult b (if n mod 2 = 0 then 1 else x))
  in f x y 1;;

let () =
  let f x y = pow x y 1000000007 |> Printf.printf "%d\n"
  in Scanf.scanf "%d %d\n" f;;