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: import os
  import sys
  
  if os.getenv("LOCAL"):
      sys.stdin = open("_in.txt", "r")
  
  sys.setrecursionlimit(2147483647)
  INF = float("inf")
  IINF = 10**18
  MOD = 10**9 + 7
  
  # 解説AC
  N = int(sys.stdin.readline())
  
  # # dp[i][j]: 右からiビット目まで決まってて、vがjとなるパターン数
  # dp = [[0] * (N + 1) for _ in range(N.bit_length())]
  # # 両方0
  # dp[0][0] += 1
  # # 片方1
  # dp[0][1] += 1
  # # 両方1
  # dp[0][2] += 1
  # for i in range(1, N.bit_length()):
  #     for j in range(N + 1):
  #         # 両方0
  #         dp[i][j] += dp[i - 1][j]
  #         # 片方1
  #         if j + pow(2, i) <= N:
  #             dp[i][j + pow(2, i)] += dp[i - 1][j]
  #         # 両方1
  #         if j + pow(2, i + 1) <= N:
  #             dp[i][j + pow(2, i + 1)] += dp[i - 1][j]
  # print(sum(dp[-1]))
  
  
  # # dp[j]: vがjとなるパターン数
  # # 上から決めてく
  # dp = [0] * (N + 1)
  # # 両方0
  # dp[0] = 1
  # # 片方1
  # dp[1 << (N.bit_length() - 1)] = 1
  # for i in reversed(range(N.bit_length() - 1)):
  #     for j in reversed(range(N + 1)):
  #         # 片方1
  #         if j + pow(2, i) <= N:
  #             dp[j + pow(2, i)] += dp[j]
  #         # 両方1
  #         if j + pow(2, i + 1) <= N:
  #             dp[j + pow(2, i + 1)] += dp[j]
  #     print(dp)
  # print(sum(dp))
  
  
  # # dp[i][j]: 右からiビット目まで決まってて、N-vがjとなるパターン数
  # # 上から決めてく
  # dp = [[0] * (N + 1) for _ in range(N.bit_length())]
  # # 両方0
  # dp[-1][-1] = 1
  # # 片方1
  # dp[-1][N - (1 << (N.bit_length() - 1))] = 1
  # for i in reversed(range(N.bit_length() - 1)):
  #     for j in reversed(range(N + 1)):
  #         # 両方0
  #         dp[i][j] += dp[i + 1][j]
  #         # 片方1
  #         if j - (1 << i) >= 0:
  #             dp[i][j - (1 << i)] += dp[i + 1][j]
  #         # 両方1
  #         if j - (1 << i + 1) >= 0:
  #             dp[i][j - (1 << i + 1)] += dp[i + 1][j]
  #     print(dp)
  # print(sum(dp[0]))
  
  # # dp[i][j]: 右からiビット目まで決まってて、(N>>i)-(v>>i)がjとなるパターン数
  # # 上から決めてく
  # dp = [[0] * (N * 3) for _ in range(N.bit_length())]
  # # 両方0
  # dp[-1][1] = 1
  # # 片方1
  # dp[-1][0] = 1
  # for i in reversed(range(N.bit_length() - 1)):
  #     for j in reversed(range(N + 1)):
  #         if N >> i & 1:
  #             # 両方0
  #             dp[i][(j << 1) + 1] += dp[i + 1][j]
  #             # 片方1
  #             dp[i][j << 1] += dp[i + 1][j]
  #             if j > 0:
  #                 # 両方1
  #                 dp[i][(j << 1) - 1] += dp[i + 1][j]
  #         else:
  #             # 両方0
  #             dp[i][j << 1] += dp[i + 1][j]
  #             if j > 0:
  #                 # 片方1
  #                 dp[i][(j << 1) - 1] += dp[i + 1][j]
  #                 # 両方1
  #                 dp[i][(j << 1) - 2] += dp[i + 1][j]
  #     print(dp)
  # print(sum(dp[0]))
  
  # dp[i][j]: 右からiビット目まで決まってて、(N>>i)-(v>>i)がjとなるパターン数
  # j >= 2 以降は j <= 1 に入ってこないので j == 2 としてまとめる
  # 上から決めてく
  dp = [[0] * 3 for _ in range(N.bit_length())]
  # 両方0
  dp[-1][1] = 1
  # 片方1
  dp[-1][0] = 1
  for i in reversed(range(N.bit_length() - 1)):
      if N >> i & 1:
          # 両方0
          # dp[i][(j << 1) + 1] += dp[i + 1][j]
          dp[i][1] += dp[i + 1][0]
          dp[i][2] += dp[i + 1][1]
          dp[i][2] += dp[i + 1][2]
          # 片方1
          # dp[i][j << 1] += dp[i + 1][j]
          dp[i][0] += dp[i + 1][0]
          dp[i][2] += dp[i + 1][1]
          dp[i][2] += dp[i + 1][2]
          # 両方1
          # dp[i][(j << 1) - 1] += dp[i + 1][j]
          dp[i][1] += dp[i + 1][1]
          dp[i][2] += dp[i + 1][2]
      else:
          # 両方0
          # dp[i][j << 1] += dp[i + 1][j]
          dp[i][0] += dp[i + 1][0]
          dp[i][2] += dp[i + 1][1]
          dp[i][2] += dp[i + 1][2]
          # 片方1
          # dp[i][(j << 1) - 1] += dp[i + 1][j]
          dp[i][1] += dp[i + 1][1]
          dp[i][2] += dp[i + 1][2]
          # 両方1
          # dp[i][(j << 1) - 2] += dp[i + 1][j]
          dp[i][0] += dp[i + 1][1]
          dp[i][2] += dp[i + 1][2]
      dp[i][0] %= MOD
      dp[i][1] %= MOD
      dp[i][2] %= MOD
  print(sum(dp[0]) % 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"}]