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 Debug.Trace

main = do
    [m,n] <- fmap (map read.words) getLine
    print $ powMod 1000000007 m n

powMod :: Int -> Int -> Int -> Int
powMod p m n = pm n
    where pm 0 = trace "call 0" 1
          pm 1 = trace "call 1" $ m `mod` p
          pm a = let n1' = a `div` 2
                     n2' = a - n1'
                  in trace ("call " ++ show a) $ (powModList !! n1' * powModList !! n2') `mod` p
          powModList = [pm x | x <- [0,1..]]
