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 Data.Word
import Debug.Trace
import Data.Array.IArray
import Data.Array.Unboxed

main = do
    [m,n] <- fmap (map read.words) getLine
    print $ powModArray 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..]]
    where pm 0 = 1
          pm 1 = m `mod` p
          pm a = let n1' = a `div` 2
                     n2' = a - n1'
                  in (powModList !! n1' * powModList !! n2') `mod` p
          powModList = [pm x | x <- [0,1..]]

powModArray :: Word32 -> Word32 -> Word32 -> Word32
powModArray p m n = pmArray ! n
    where
        pmArray = array (0,1000000000) $ zip [0..] $ pmlist :: UArray Word32 Word32
        pmlist :: [Word32]
        pmlist = [pm x | x <- [0..1]]
        pm n'
          | n' == 0 = trace "call 0" 1
          | n' == 1 = trace "call 1" $ m `mod` p
          | otherwise = let n1 = n' `div` 2
                            n2 = n' - n1
                         in trace ("call " ++ show n') $ (pmArray ! n1 * pmArray ! n2) `mod` p

