import Data.Tuple
import Data.List

data Tree a = Node a (Tree a) (Tree a)
memoize f = memof where memof = f (query (blank memof))
blank f = blank' 1 where blank' k = Node (f k) (blank' (2*k)) (blank' (2*k+1))

query m x = query' m bits
 where
  bits = reverse (take w (unfoldr (return . swap . flip divMod 2) x))
  w = floor (logBase 2 (fromIntegral x))
  query' (Node v left right) bs
   | bs == [] = v
   | head bs == 0 = query' left (tail bs)
   | otherwise = query' right (tail bs)

main = readLn >>= print . fib
fib = memoize $ \f n -> if n < 2 then n else f (n-1) + f (n-2)