{-# LANGUAGE NumericUnderscores #-} import Control.Monad import Control.Monad.Fix import Data.Bool import Data.IORef main :: IO () main = do [a, b, n] <- map read . words <$> getLine let c = bool ((a + 1_000_000_007) `div` 2) (a `div` 2) (even a) det = (c * c `mod` 1_000_000_007 + b) `mod` 1_000_000_007 alp = (c, 1) xp = (1, 0) x <- newIORef xp cache <- newIORef alp flip fix n $ \loop i -> do when (odd i) $ do ca <- readIORef cache modifyIORef' x (\i -> mul i ca det) modifyIORef' cache (\i -> mul i i det) when (i > 0) $ loop (i `div` 2) (_, q) <- readIORef x print q mul :: (Int, Int) -> (Int, Int) -> Int -> (Int, Int) mul (a, b) (c, d) det = let p = (a * c `mod` 1_000_000_007 + det * (b * d `mod` 1_000_000_007) `mod` 1_000_000_007) `mod` 1_000_000_007 q = (a * d `mod` 1_000_000_007 + b * c `mod` 1_000_000_007) `mod` 1_000_000_007 in (p, q)