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: MOD = int(10**9)+7
  N = int(input())
  
  dp[0][0] = 1
  for i in range(64,-1,-1):
    ndp = [0,0,0]
    for d in range(3):
      nd = d*2 + (N>>>i&1)
      ndp[min(2,nd)] += dp[d]
      if nd >= 1: ndp[min(2,nd-1)] += dp[d]
      if nd >= 2: ndp[min(2,nd-2)] += dp[d]
    dp = ndp
    
  print(sum(dp) % 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"}]