modexp :: Integral a => a -> a -> a -> a
modexp b ex m
    | ex == 0   = 1
    | even ex   = flip mod m $ square $ flip mod m $ modexp b (div ex 2) m 
    | otherwise = flip mod m $ mod b m * (flip mod m $ modexp b (ex - 1) m)
    where square x = x * x

main :: IO ()
main = print . (\(n : m : _) -> modexp n m 129402307) . map read . lines =<< getContents