{-# LANGUAGE BangPatterns  #-}
{-# LANGUAGE CPP           #-}
{-# LANGUAGE MagicHash     #-}
{-# LANGUAGE UnboxedTuples #-}

import GHC.Exts

#define MOD  1000000007
#define MOD2 2000000016

main :: IO ()
main = readLn >>= print . fib1 . fib2

infixl 7 *%, *%%
infixl 6 +%, +%%, -%, -%%

(+%) :: Int -> Int -> Int
(I# x#) +% (I# y#) = case x# +# y# of
    r# -> I# (r# -# ((r# >=# MOD#) *# MOD#))
{-# INLINE (+%) #-}

(-%) :: Int -> Int -> Int
(I# x#) -% (I# y#) = case x# -# y# of
    r# -> I# (r# +# ((r# <# 0#) *# MOD#))
{-# INLINE (-%) #-}

(*%) :: Int -> Int -> Int
(I# x#) *% (I# y#) = case timesWord# (int2Word# x#) (int2Word# y#) of
  z# -> case timesWord2# z# im# of
    (# q#, _ #) -> case minusWord# z# (timesWord# q# m#) of
      v#  | isTrue# (geWord# v# m#) -> I# (word2Int# (plusWord# v# m#))
          | otherwise -> I# (word2Int# v#)
  where
    m# = int2Word# MOD#
    im# = plusWord# (quotWord# 0xffffffffffffffff## m#) 1##
{-# INLINE (*%) #-}

(+%%) :: Int -> Int -> Int
(I# x#) +%% (I# y#) = case x# +# y# of
    r# -> I# (r# -# ((r# >=# MOD2#) *# MOD2#))
{-# INLINE (+%%) #-}

(-%%) :: Int -> Int -> Int
(I# x#) -%% (I# y#) = case x# -# y# of
    r# -> I# (r# +# ((r# <# 0#) *# MOD2#))
{-# INLINE (-%%) #-}

(*%%) :: Int -> Int -> Int
(I# x#) *%% (I# y#) = case timesWord# (int2Word# x#) (int2Word# y#) of
  z# -> case timesWord2# z# im# of
    (# q#, _ #) -> case minusWord# z# (timesWord# q# m#) of
      v#  | isTrue# (geWord# v# m#) -> I# (word2Int# (plusWord# v# m#))
          | otherwise -> I# (word2Int# v#)
  where
    m# = int2Word# MOD2#
    im# = plusWord# (quotWord# 0xffffffffffffffff## m#) 1##
{-# INLINE (*%%) #-}

fastDoubling1 :: Int -> (Int, Int)
fastDoubling1 0 = (0, 1)
fastDoubling1 1 = (1, 1)
fastDoubling1 i
  = let (a, b) = fastDoubling1 (i `quot` 2)
    in if even i
       then (a *% (2 *% b -% a), a *% a +% b *% b)
       else (a *% a +% b *% b, b *% (2 *% a +% b))

fib1 :: Int -> Int
fib1 i = case fastDoubling1 i of
          (a, _) -> a `mod` MOD

fastDoubling2 :: Int -> (Int, Int)
fastDoubling2 0 = (0, 1)
fastDoubling2 1 = (1, 1)
fastDoubling2 i
  = let (a, b) = fastDoubling2 (i `quot` 2)
    in if even i
       then (a *%% (2 *%% b -%% a), a *%% a +%% b *%% b)
       else (a *%% a +%% b *%% b, b *%% (2 *%% a +%% b))

fib2 :: Int -> Int
fib2 i = case fastDoubling2 i of
          (a, _) -> a `mod` MOD2