import qualified Data.IntMap.Strict as M

main = interact $ show . sol . read

sol = fst . f M.empty

f m 0 = (1,M.insert 0 1 m)
f m 1 = (2,M.insert 1 2 m)
f m n
  | n `M.member` m  = (m M.! n,m)
  | otherwise       = (a,M.insert n a m1)
  where
  k = n `div` 2
  (a0,m0) = f m k
  (a1,m1) = f m0 (k-1)
  a = (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..