import Control.Monad
import Data.List
import Data.Monoid
import Data.IORef

unwrap [x] = x

initlist :: Int -> [Integer]
initlist n
    | (n == 0) = [0]
    | otherwise = 0 : (initlist (n - 1))

data Tree a = Leaf a | Node Int (Tree a) (Tree a)



setnode :: Num a => Tree a -> Tree a -> Tree a
setnode xt yt = Node (lsize xt) xt yt

lsize :: Num a => Tree a -> Int
lsize (Leaf x) = 1
lsize (Node n xt yt) = n + lsize yt

buildtree :: Num a => [a] -> Tree a
buildtree xs
    | (m == 0) = Leaf (unwrap xs)
    | otherwise = setnode (buildtree ys) (buildtree zs)
    where
        m = (length xs) `div` 2
        (ys,zs) = splitAt m xs

getval :: Num a => Tree a -> Int -> a
getval (Leaf x) 0 = x
getval (Node n xs ys) k = if k < n then getval xs k else getval ys (k - n)

updval :: Num a => Tree a -> Int -> a -> Tree a
updval (Leaf x) 0 k = (Leaf k)
updval (Node n xs ys) i k = if i < n then Node n (updval xs i k) ys else Node n xs (updval ys (i - n) k)

main = do
    n <- readLn
    let a = initlist n
    ar <- newIORef (buildtree a)
    rt1 <- readIORef ar
    writeIORef ar (updval rt1 0 2)
    rt2 <- readIORef ar
    writeIORef ar (updval rt2 1 1)
    when (n >= 2) $ do
        forM_ [2..n] $ \i -> do
            rt <- readIORef ar
            let v1 = getval rt (i - 1)
            let v2 = getval rt (i - 2)
            writeIORef ar (updval rt i (v1 + v2))
    rt3 <- readIORef ar
    print $ getval rt3 n