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: n = int(input())
  mod = 10**9 + 7
  bt = bin(n)[2:]
  k = len(bt)
  dp = [[0] * 2 for i in range(k + 1)]
  dp[0][0] = 1
  dp[0][1] = 1
  for i in range(k):
      j = int(bt[k - i - 1])
      a, b, c = [(1, 0, 0), (1, 1, 0)][j]
      d, e, f = [(1, 1, 1), (0, 1, 2)][j]
      dp[i + 1][0] = (a * dp[i][0] + b * dp[i][1] + c * (3**i)) % mod
      dp[i + 1][1] = (d * dp[i][0] + e * dp[i][1] + f * (3**i)) % mod
  print(dp[k][0])
  
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"}]