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: # -*- coding: utf-8 -*-
  
  import sys
  
  
  def input():
      return sys.stdin.readline().strip()
  
  
  def list2d(a, b, c):
      return [[c] * b for i in range(a)]
  
  
  def list3d(a, b, c, d):
      return [[[d] * c for j in range(b)] for i in range(a)]
  
  
  def list4d(a, b, c, d, e):
      return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
  
  
  def ceil(x, y=1):
      return int(-(-x // y))
  
  
  def INT():
      return int(input())
  
  
  def MAP():
      return map(int, input().split())
  
  
  def LIST(N=None):
      return list(MAP()) if N is None else [INT() for i in range(N)]
  
  
  def Yes():
      print("Yes")
  
  
  def No():
      print("No")
  
  
  def YES():
      print("YES")
  
  
  def NO():
      print("NO")
  
  
  sys.setrecursionlimit(10**9)
  INF = float("inf")
  MOD = 10**9 + 7
  
  N = INT()
  N = format(N, "060b")[::-1]
  # N[i] := Nのiビット目としておく
  N = [0] + list(map(int, N))
  
  # dp[i][j] := iビット目まで見て、その桁までの値において、a+b がNより j*2^i 小さい通り数(j>=2はj=2で同一視)
  dp = list2d(61, 3, 0)
  dp[60][0] = 1
  for i in range(60, 0, -1):
      # jの状態 j=0,1,2以上 の3通り
      for j in range(3):
          # 今回の桁でのa,bの選び方 (0,0)=0,(0,1)=1,(1,1)=2 の3通り
          for k in range(3):
              # 1桁下がる時に、現在のjは 2^i = 2*2^(i-1) から、*2される
              # Nのビットが立っている桁なら1を足す
              # 今回追加するk(0~2)を引く
              nxt = min(j * 2 + N[i] - k, 2)
              # nxtがマイナスなら繰り上がりでNを超えるので遷移させない
              if nxt >= 0:
                  dp[i - 1][nxt] += dp[i][j]
                  dp[i - 1][nxt] %= MOD
  print((dp[0][0] + dp[0][1] + dp[0][2]) % 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"}]