{-# LANGUAGE BangPatterns #-}

import           Data.Bool
import           Data.List
import qualified GHC.Integer.GMP.Internals         as GMP

main :: IO ()
main = do
  [a, b, n] <- map read . words <$> getLine
  print $ tetration a b n

tetration :: Int -> Int -> Int -> Int
tetration a b m
  | m == 1 = 0
  | a == 0 = bool 0 1 (even b)
  | b == 0 = 1
  | b == 1 = a `mod` m
  | b == 2 = powModInt (a `mod` m) a m
  | a == 2 && b == 3 = 16 `mod` m
  | otherwise = powModInt (a `mod` m) (prev + phi) m
  where
    !phi = totient m
    prev = tetration a (b - 1) phi

powModInt :: Int -> Int -> Int -> Int
powModInt a b c = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral b) (fromIntegral c)
{-# INLINE powModInt #-}

totient :: Int -> Int
totient n = n `quot` product ps * (product $ map (subtract 1) ps)
  where ps = map head . group $ primeFactors n

smallPrimes :: [Int]
smallPrimes = 2 : [ n | n <- [3, 5 .. 46337], all ((0 <) . rem n) $ takeWhile (\x -> x * x <= n) smallPrimes]

primeFactors :: Int -> [Int]
primeFactors n | n < 2 = []
primeFactors n = go n smallPrimes
  where
    go !n pps@(p:ps)
      | n < p * p = [n]
      | r > 0     = go n ps
      | otherwise = p : go q pps
      where
        (q, r) = quotRem n p
    go n [] = [n]