{-# LANGUAGE FlexibleContexts #-}

import Control.Monad.Memo

main = interact $ show . sol . read

sol = startEvalMemo . f

f :: (MonadMemo a Int m, Integral a) => a -> m Int
f 0 = return 1
f 1 = return 2
f n = do
  let k = n `div` 2
  a0 <- memo f k
  a1 <- memo f (k-1)
  return $ (if odd n then 2*a0+a1 else a0+2*a1) `mod` p

p = 10^9+7 :: Int

-- OEIS A007729	: 6th binary partition function.
-- a(2k) = 2*a(k-1) + a(k); a(2k+1) = 2*a(k) + a(k-1)
-- 1, 2, 4, 5, 8, 10, 13, 14, 18, 21, 26, 28, 33, 36, 
-- 40, 41, 46, 50, 57, 60, 68, 73, 80, 82, 89, 94..