powmod' :: Int -> Int -> Int -> Int -> Int powmod' a 0 m ret = ret powmod' a k m ret | odd k = let ret' = mod (ret * a) m in powmod' (mod (a ^ 2) m) (k `div` 2) m ret' | otherwise = powmod' (mod (a ^ 2) m) (k `div` 2) m ret powmod :: Int -> Int -> Int -> Int powmod a k m = powmod' a k m 1 main = do str <- getLine let [a, b, c] = map read $ splitBy '^' str :: [Int] let p = 10^9 + 7 let ab_c = powmod (powmod a b p) c p let a_bc = powmod a (powmod b c p) p putStrLn (show ab_c ++ " " ++ show a_bc) splitBy delimiter = foldr f [[]] where f c l@(x:xs) | c == delimiter = []:l | otherwise = (c:x):xs