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 Control.Applicative

pow :: Int -> Int -> Int
pow m n = pow' m n 1

pow' :: Int -> Int -> Int -> Int
pow' m n oddtime
    | n == 0 = oddtime
    | even n = pow' (m*m) (n `div` 2) oddtime
    | odd n = pow' (m*m) (n `div` 2) (oddtime*m)

main = do
    [m, n] <- words <$> getLine
    putStrLn $ show $ (pow (read m::Int) (read n::Int)) `mod` 1000000007