output_description: Print the number of the possible pairs of integers u and v, modulo 10^9+7.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N
attempt: from collections import defaultdict, deque, Counter
  from heapq import heappush, heappop, heapify
  from bisect import bisect_right, bisect_left
  import random
  from itertools import permutations, accumulate, combinations, product
  import sys
  import string
  from bisect import bisect_left, bisect_right
  from math import factorial, ceil, floor, gamma, log
  from operator import mul
  from functools import reduce
  
  
  sys.setrecursionlimit(2147483647)
  INF = float("INF")
  
  
  def LI():
      return list(map(int, sys.stdin.buffer.readline().split()))
  
  
  def I():
      return int(sys.stdin.buffer.readline())
  
  
  def LS():
      return sys.stdin.buffer.readline().rstrip().decode("utf-8").split()
  
  
  def S():
      return sys.stdin.buffer.readline().rstrip().decode("utf-8")
  
  
  def IR(n):
      return [I() for i in range(n)]
  
  
  def LIR(n):
      return [LI() for i in range(n)]
  
  
  def SR(n):
      return [S() for i in range(n)]
  
  
  def LSR(n):
      return [LS() for i in range(n)]
  
  
  def SRL(n):
      return [list(S()) for i in range(n)]
  
  
  def MSRL(n):
      return [[int(j) for j in list(S())] for i in range(n)]
  
  
  mod = 1000000007
  
  
  n = I()
  dp = [[0] * 3 for _ in range(62)]
  dp[0][0] = 1
  for i in range(61):
      zero, one, two = dp[i]
      if n >> (60 - i) & 1:
          zero, one, two = zero, zero + one, 2 * one + 3 * two
      else:
          zero, one, two = zero + one, one, one + 3 * two
      dp[i + 1] = [zero % mod, one % mod, two % mod]
  
  
  print(sum(dp[-1]) % mod)
  
problem_description: Statement
  
  You are given a positive integer N. Find the number of the pairs of integers u
  and v (0≦u,v≦N) such that there exist two non-negative integers a and b
  satisfying a xor b=u and a+b=v. Here, xor denotes the bitwise exclusive OR.
  Since it can be extremely large, compute the answer modulo 10^9+7.
samples: [{"input": "3", "output": "5\n    \n\nThe five possible pairs of u and v are:\n\n  * u=0,v=0 (Let a=0,b=0, then 0 xor 0=0, 0+0=0.)\n\n  * u=0,v=2 (Let a=1,b=1, then 1 xor 1=0, 1+1=2.\uff09\n\n  * u=1,v=1 (Let a=1,b=0, then 1 xor 0=1, 1+0=1.\uff09\n\n  * u=2,v=2 (Let a=2,b=0, then 2 xor 0=2, 2+0=2.\uff09\n\n  * u=3,v=3 (Let a=3,b=0, then 3 xor 0=3, 3+0=3.\uff09\n\n* * *"}, {"input": "1422", "output": "52277\n    \n\n* * *"}, {"input": "1000000000000000000", "output": "787014179"}]