import Data.Bits

main :: IO ()
main = readLn >>= print . fib

fastDoubling :: Int -> (Integer, Integer)
fastDoubling 0 = (0, 1)
fastDoubling 1 = (1, 1)
fastDoubling i
  = let
      (a, b) = fastDoubling (unsafeShiftR i 1)
    in
      if even i
        then (a * (2 * b - a), a * a + b * b)
        else (a * a + b * b, b * (2 * a + b))

fib :: Int -> Integer
fib i = case fastDoubling i of
          (a, _) -> a