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
  
  ANSLIST = [1]
  for i in range(61):
      ANSLIST.append((ANSLIST[-1] * 3 - 1) % mod)
  
  ANS = [1, 2, 4, 5]
  ANSDICT = dict()
  
  
  def ans(k):
      if 0 <= k <= 3:
          return ANS[k]
      if ANSDICT.get(k) != None:
          return ANSDICT[k]
      for i in range(61):
          if k == 2**i - 2:
              return ANSLIST[i] - 1
          if k == 2**i - 1:
              return ANSLIST[i]
          if 2**i - 1 > k:
              break
      x = k - (2 ** (i - 1) - 1)
  
      ANSDICT[k] = (ans(x - 1) + ANSLIST[i - 1] * 2 - ans(2 ** (i - 1) - x - 2) - 1) % mod
      return ANSDICT[k]
  
  
  print(ans(N))
  
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"}]