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.

-----Constraints-----
 - 1≦N≦10^{18}

-----Input-----
The input is given from Standard Input in the following format:
N

-----Output-----
Print the number of the possible pairs of integers u and v, modulo 10^9+7.

-----Sample Input-----
3

-----Sample Output-----
5

The five possible pairs of u and v are:
 - u=0,v=0 (Let a=0,b=0, then 0 xor 0=0, 0+0=0.)
 - u=0,v=2 (Let a=1,b=1, then 1 xor 1=0, 1+1=2.）
 - u=1,v=1 (Let a=1,b=0, then 1 xor 0=1, 1+0=1.）
 - u=2,v=2 (Let a=2,b=0, then 2 xor 0=2, 2+0=2.）
 - u=3,v=3 (Let a=3,b=0, then 3 xor 0=3, 3+0=3.）

Difficulty: interview

Starter code:

Solutions:
import sys

in1 = sys.stdin.readlines()
N = int(in1[0])
#N = 10 ** 18
#N = 2
"""
0 + 0 = 0
0 x 0 = 0

1 + 0 = 1
1 x 0 = 1

2 + 0 = 2
2 x 0 = 2
1 + 1 = 2
1 x 1 = 0

3 + 0 = 3
3 x 0 = 3
2 + 1 = 3
2 x 1 = 3
"""
p = 10 ** 9 + 7

def f(n):
    if n in d:
        return d[n]
    d[n] = f(n // 2) + f((n - 1) // 2) + f((n - 2) // 2)
    return d[n]

d = {0: 1, 1: 2}
print((f(N) % p))


def solve(n: int) -> int:
    mod = 1e9 + 7
    n_bin = '0' + bin(n)[2:]

    dp = [[0, 0, 0] for _ in range(len(n_bin))]
    dp[-1][0] = 1
    for i in range(len(n_bin) - 2, -1, -1):
        for s in range(3):
            for k in range(3):
                s2 = min(2, 2 * s + int(n_bin[len(n_bin) - i - 1]) - k)
                if s2 >= 0:
                    dp[i][s2] = int((dp[i][s2] + dp[i + 1][s]) % mod)

    return int(sum(dp[0]) % mod)

n = int(input())
print(solve(n))

MOD = 10**9+7

n = int(input())
s = bin(n)[2:]
l = len(s)
dp = [[0]*4 for i in range(l+1)]
dp[0][0] = 1

for i in range(l):
    b = 1 if s[i] == '1' else 0
    for j in range(4):
        for k in range(3):
            lj = min((j<<1) + b - k, 3)
            if 0 <= lj:
                dp[i+1][lj] += dp[i][j]
                dp[i+1][lj] %= MOD

# print(dp)
print((sum(dp[l])%MOD))


MOD = 10 ** 9 + 7
N = int(input())
M = len(bin(N)) - 2
L = bin(N)[2:]

dp = [[0] * 3 for _ in range(M + 1)]
dp[0][0] = 1

for i in range(M):
    if L[i] == '1':
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][0] + dp[i][1]
        dp[i + 1][2] += 2 * dp[i][1] + 3 * dp[i][2]
    else:
        dp[i + 1][0] += dp[i][0] + dp[i][1]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][1] + 3 * dp[i][2]
    
    for j in range(3):
        dp[i + 1][j] %= MOD


print((sum(dp[M]) % MOD))


from functools import*
@lru_cache(None)
def d(n):x=n//2;return n+1 if n<2 else d(x)+d(~-x)+d(n+~x)
print(d(int(input()))%(10**9+7))

N=int(input())
s=bin(N)[2:]
K=len(s)
mod=10**9+7
#bp[i][j]は上からiビット以上が確定でN>>(K-i)-v>>(K-i)=jとなる通り数
bp=[[0]*(3) for i in range(K+1)]
bp[0][0]=1
for i in range(1,K+1):
    if s[i-1]=="0":
        bp[i][0]=(bp[i-1][1]+bp[i-1][0])%mod
        bp[i][1]=bp[i-1][1]
        bp[i][2]=(bp[i-1][1]+bp[i-1][2]*3)%mod
    else:
        bp[i][0]=bp[i-1][0]
        bp[i][1]=(bp[i-1][1]+bp[i-1][0])%mod
        bp[i][2]=(bp[i-1][1]*2+bp[i-1][2]*3)%mod
print((sum(bp[-1])%mod))


# python3 (3.4.3)
import sys
input = sys.stdin.readline

# main
N = int(input())

mod = 10**9+7
# bitも上から見ていくので逆順にして扱いやすくする
binN = format(N,"061b")[::-1]

dp = [[0,0,0] for _ in range(61)]
dp[60][0] = 1

for i in range(59,-1,-1):
    # i桁目のbitが 1
    if binN[i]=="1":
        dp[i][0] = dp[i+1][0]
        dp[i][1] = dp[i+1][0] + dp[i+1][1]
        dp[i][2] = 2*dp[i+1][1] + 3*dp[i+1][2]
    # i桁目のbitが 0
    else:
        dp[i][0] = dp[i+1][0] + dp[i+1][1]
        dp[i][1] = dp[i+1][1]
        dp[i][2] = dp[i+1][1] + 3*dp[i+1][2]

    for j in range(3):
        dp[i][j] %= mod

print((dp[0][0] + dp[0][1] + dp[0][2]) % mod)

P=10**9+7
inv2=(1+P)//2
def exp(a,k):
    if k==0:
        return 1
    elif k%2==0:
        return (exp(a*a,k//2))%P
    else:
        return (a*exp(a*a,k//2))%P
D=dict()
def f(N):
    if N in D:
        return D[N]
    if N<=1:
        D[N]=N
        return N
    i=0
    while(1):
        if 2**i<=N<2**(i+1):
            break
        i+=1
    if N==2**i:
        D[N]=((1+exp(3,i))*inv2)%P
        return D[N]
    D[N]=(f(N-2**i)-f(2**(i+1)-N-1)+exp(3,i))%P
    return D[N]
print(f(int(input())+1))

def d_xor_sum(N):
    from functools import lru_cache

    @lru_cache()
    def f(k):
        # a+b<=k,a xor b <= k を満たす正整数(a,b)の組の個数(ただしa>=b)
        # N=0のとき(u,v)の組は(0,0)の1通り
        # N=1のとき(0,0),(1,1)の2通り
        return (1, 2)[k] if k <= 1 else f(k // 2) + f((k - 1) // 2) + f((k - 2) // 2)

    ans = f(N) % (10**9 + 7)
    return ans

N = int(input())
print(d_xor_sum(N))

MOD=10**9+7
N = int(input())
K = len(bin(N)) - 2
DP = [[0]*3 for _ in range(K+1)]
DP[0][0] = 1
for k in range(K):
    if N & (1 << K - k - 1):
        DP[k+1][0] = DP[k][0]
        DP[k+1][1] = (DP[k][0] + DP[k][1]) % MOD
        DP[k+1][2] = (DP[k][1]*2 + DP[k][2]*3) % MOD
    else:
        DP[k+1][0] = (DP[k][0] + DP[k][1]) % MOD
        DP[k+1][1] = DP[k][1]
        DP[k+1][2] = (DP[k][1] + DP[k][2]*3) % MOD
print(sum(DP[-1]) % MOD)

N = int(input())
a, b, c = 1, 0, 0
for i in range(80)[::-1]:
    if N>>i & 1: a, b, c = a, a+b, 2*b+3*c
    else: a, b, c = a+b, b, b+3*c
print((a+b+c) % (10**9+7))

MOD = 10**9+7
n = int(input())
s = bin(n)[2:]
dp = [[0, 0, 0] for _ in range(len(s) + 1)]
dp[0][0] = 1
for i in range(len(s)):
    if s[i] == '0':
        dp[i + 1][0] = dp[i][0] + dp[i][1]
        dp[i + 1][1] = dp[i][1]
        dp[i + 1][2] = dp[i][1] + dp[i][2] * 3
    else:
        dp[i + 1][0] = dp[i][0]
        dp[i + 1][1] = dp[i][0] + dp[i][1]
        dp[i + 1][2] = dp[i][1] * 2 + dp[i][2] * 3
    for j in range(3):
        dp[i+1][j] %= MOD
print((sum(dp[-1])%MOD))


n = int(input())
x = n.bit_length()
dp = [[0]*3 for i in range(x)]
dp[-1][0] = 1
dp[-1][1] = 1
mod = 10**9+7

for i in range(x-2,-1,-1):

    if (n >> i) & 1:
        dp[i][0] = (dp[i+1][0])%mod
        dp[i][1] = (dp[i+1][0]+dp[i+1][1])%mod
        dp[i][2] = (dp[i+1][2]*3+dp[i+1][1]*2)%mod

    else:
        dp[i][0] = (dp[i+1][0]+dp[i+1][1])%mod
        dp[i][1] = (dp[i+1][1])%mod
        dp[i][2] = (dp[i+1][2]*3+dp[i+1][1])%mod
print(sum(dp[0])%mod)

MOD=10**9+7
N=int(input())

dp=[[0 for _ in range(3)] for _ in range(64)]
dp[63][0]=1

for d in range(62,-1,-1):
  b=(N>>d)&1 
  s=dp[d+1][:]
  dp[d][0]=dp[d+1][0]+(1^b)*dp[d+1][1] % MOD
  dp[d][1]=b*dp[d+1][0]+dp[d+1][1] % MOD
  dp[d][2]=(1+b)*dp[d+1][1]+3*dp[d+1][2] % MOD

print(sum(dp[0][:]) % MOD)

from functools import lru_cache

mod = 10 ** 9 + 7

@lru_cache(maxsize=None)
def f(n):
    if n <= 1:
        return n + 1
    return (f(n // 2) + f((n - 1) // 2) + f((n - 2) // 2)) % mod

N = int(input())
print(f(N))

n = int(input())
bn = bin(n)[2:]
dp = [[0]*3 for i in range(len(bn) + 1)]
mod = 10**9+7
dp[len(bn)][0] = 1
for d in range(len(bn)-1, -1, -1):
    if bn[len(bn)-1 - d] == "1":
        dp[d][0] = dp[d+1][0]
        dp[d][1] = dp[d+1][0] + dp[d+1][1]
        dp[d][2] = 2*dp[d+1][1] + 3*dp[d+1][2]
    else:
        dp[d][0] = dp[d+1][0] + dp[d+1][1]
        dp[d][1] = dp[d+1][1]
        dp[d][2] = dp[d+1][1] + 3*dp[d+1][2]
print((dp[0][0] + dp[0][1] + dp[0][2]) % mod)


MOD = 10**9+7
n = int(input())

dp = [1,0,0]
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] # 0,0
        if nd >= 1: ndp[min(2,nd-1)] += dp[d] # 0,1
        if nd >= 2: ndp[min(2,nd-2)] += dp[d] # 1,1
    dp = ndp
    
print((sum(dp) % MOD))


#!/usr/bin/env python3
N = int(input())

MOD = 1000000007
cache = {0: 1, 1: 2}


def f(n):
    if n in cache:
        return cache[n]
    if n % 2 == 0:
        result = 2 * f(n // 2 - 1) + f(n // 2)
    else:
        result = f(n // 2 - 1) + 2 * f(n // 2)
    result %= MOD
    cache[n] = result
    return result


print((f(N)))


cache = {}
M = 10**9+7
def f(i):
    if i == 0: return 0
    if i == 1: return 1
    if i in cache: return cache[i]
    k = i//2
    if i % 2 == 0: cache[i] = 2*f(k)%M + f(k-1)%M
    else: cache[i] = 2*f(k)%M + f(k+1)%M
    cache[i] %= M
    return cache[i]
print((f(int(input())+1)))


import sys

p=10**9+7
dthbit=lambda d,n: (n>>d)&1

def main(n):
    dp=[[0 for _ in range(3)] for _ in range(64)]
    dp[63][0]=1
    for d in range(62,-1,-1):
        b=dthbit(d,n)
        s=dp[d+1][:]
        dp[d][0]=dp[d+1][0]+(1^b)*dp[d+1][1] % p
        dp[d][1]=b*dp[d+1][0]+dp[d+1][1] % p
        dp[d][2]=(1+b)*dp[d+1][1]+3*dp[d+1][2] % p
    return sum(dp[0][:]) % p

n=int(input())
print((main(n)))


# coding: utf-8
# Your code here!
odd={0:1}
even={0:1,1:3}
M=10**9+7
def memo(N):
    if N ==0:
        return 1
    if N==1:
        return 2
    return (memoodd((N-1)//2)+memoeven(N//2))%M

def memoodd(N):
    if N in odd:
        return odd[N]
    odd[N] = memo(N)
    return odd[N]

def memoeven(N):
    if N in even:
        return even[N]
    even[N] = (memo(N)+memo(N-1))%M
    return even[N]

n=int(input())
print((memo(n)))


N = int(input())
MOD = 10**9+7
dp = [[0]*3 for _ in range(61)]
dp[60][0] = 1
for d in range(59,-1,-1):
    for s in range(3):
        for k in range(3):
            ns = min(2, 2*s + ((N>>d)&1) - k)
            if ns < 0: continue
            dp[d][ns] += dp[d+1][s]
            dp[d][ns] %= MOD
print(sum(dp[0]) % MOD)

from functools import lru_cache


@lru_cache(None)
def f(n):
    if n == 0:
        return 1
    elif n == 1:
        return 2
    elif n % 2 == 0:
        return (2 * f(n // 2 - 1) + f(n // 2)) % 1000000007
    else:
        return (2 * f(n // 2) + f(n // 2 - 1)) % 1000000007


n = int(input())
print(f(n))

# solution

data= int(input())

array = format(data,"b")

mod = 1000000007

dynamic = [[0 for j in range(3)] for i in range(len(array)+1)]
dynamic[0][0] = 1

for i in range(len(array)):
  for j in range(3):
      for x in range(2):
        for y in range(x,2):
          b=(data>>i)&1
          dynamic[i+1][(x+y+j-b+1)//2] = (dynamic[i+1][(x+y+j-b+1)//2]+dynamic[i][j])%mod
print(dynamic[len(array)][0])

N = int(input())
MOD = 10**9+7
dp = [[0]*3 for _ in range(61)]
dp[60][0] = 1
for d in range(59,-1,-1):
  for s in range(3):
    for k in range(3):
      ns = min(2, 2*s + ((N>>d)&1) - k)
      if ns < 0:
        continue
      dp[d][ns] += dp[d+1][s]
      dp[d][ns] %= MOD

print(sum(dp[0])%MOD)

n= int(input())
a = format(n,"b")
mod = 1000000007
dp = [[0 for j in range(3)] for i in range(len(a)+1)]
dp[0][0] = 1
for i in range(len(a)):
  for j in range(3):
      for x in range(2):
        for y in range(x,2):
          b=(n>>i)&1
          dp[i+1][(x+y+j-b+1)//2] = (dp[i+1][(x+y+j-b+1)//2]+dp[i][j])%mod
print(dp[len(a)][0])

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(list(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))


def f(n):
 if n in d:return d[n]
 d[n]=f(n//2)+f((n-1)//2)+f((n-2)//2);return d[n]
d={0:1,1:2};print(f(int(input()))%(10**9+7))

# coding: utf-8
# Your code here!
dic_memo={0:1,1:2}
M=10**9+7
def memo(N):
    if N in dic_memo:
        return dic_memo[N]
    dic_memo[N]=(memo((N-1)//2)+memo(N//2)+memo(N//2-1))%M
    return dic_memo[N]

n=int(input())
print((memo(n)))


N = int(input())
s = bin(N)[2:]
n = len(s)
dp = [[0] * 4 for i in range(len(s)+1)]
dp[0][0] = 1
MOD = int(1e9) + 7
for i in range(n):
    b = 1 if s[i] == '1' else 0
    for j in range(4):
        for k in range(3):
            nj = min(((j << 1) + b - k, 3))
            if 0 <= nj:
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
print((sum(dp[n]) % MOD))


def d_XorSum(N):
    MOD = 10**9 + 7
    memo = {0: 1, 1: 2}
    # N=0のとき(u,v)の組は(0,0)の1通り
    # N=1のとき(0,0),(1,1)の2通り

    def f(k):
        # a+b<=k,a xor b <= k を満たす正整数(a,b)の組の個数(ただしa>=b)
        if k in memo:
            return memo[k]
        ret = (f(k // 2) + f((k - 1) // 2) + f((k - 2) // 2)) % MOD
        memo[k] = ret
        return ret
    return f(N)

N = int(input())
print(d_XorSum(N))

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))

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def f(x, s):
    if min(x, s) < 0: return 0
    if max(x, s) < 2:
        if x and s: return 2
        else: return 1
    if (x, s) in memo: return memo[x, s]
    res = f(x >> 1, s >> 1) + f(x - 1 >> 1, s - 1 >> 1) + f(x >> 1, s - 2 >> 1)
    res = memo[x, s] = res % md
    return res

memo = {}
md = 10 ** 9 + 7

def main():
    n = II()
    print(f(n, n))

main()


mod = 10 ** 9 + 7

N = int(input())

memo = {0:1, 1:2}
def f(n):
    if n not in memo:
        memo[n] = (f(n // 2) + f((n - 1) // 2) + f((n - 2) // 2)) % mod
    return memo[n]

print(f(N))

N = int(input())

d = {0: 1, 1: 2}

def f(n):
  if n in d:
    return d[n]
  d[n] = (f(n // 2) + f((n - 1) // 2) + f((n - 2) // 2)) % (10**9 + 7)
  return d[n]

print(f(N))

n = int(input())

MOD = 10 ** 9 + 7

k = len(bin(n)) - 2

dp = [[0, 0, 0] for _ in range(k + 1)]

dp[0][0] = 1

for i in range(k):
    if (n >> (k - 1 - i)) & 1:
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][0] + dp[i][1]
        dp[i+1][2] = dp[i][1] * 2 + dp[i][2] * 3
    else:
        dp[i+1][0] = dp[i][0] + dp[i][1]
        dp[i+1][1] = dp[i][1]
        dp[i+1][2] = dp[i][1] + dp[i][2] * 3
    map(lambda x:x%MOD, dp[k])

print(sum(dp[k]) % MOD)

n=int(input())
nstr=bin(n)[2:]
thrpow=[1]
now=1
for k in range(len(nstr)):
    now=(now*3)%(10**9+7)
    thrpow.append(now)
f=dict()
g=dict()
if nstr[-1]=='0':f[1]=1
elif nstr[-1]=='1':f[1]=2
g[1]=3
for k in range(2,len(nstr)+1):
    if nstr[-k]=='0':
        f[k]=(f[k-1])%(10**9+7)
        g[k]=(thrpow[k-1]+f[k-1]+g[k-1])%(10**9+7)
    if nstr[-k]=='1':
        f[k]=(f[k-1]+g[k-1])%(10**9+7)
        g[k]=(2*thrpow[k-1]+g[k-1])%(10**9+7)
print(f[len(nstr)])

n = int(input())
d = len(bin(n)) - 2
mod = 10**9 + 7
dp = [[0 for j in range(3)] for i in range(d+1)]
dp[d][0] = 1
for i in range(d):
    k = d - 1 - i
    for j in range(3):
        if j == 0:
            if (n >> k) & 1:
                dp[k][0] += dp[k+1][0]
                dp[k][1] += dp[k+1][0]
            else:
                dp[k][0] += dp[k+1][0]
        elif j == 1:
            if (n >> k) & 1:
                dp[k][1] += dp[k+1][1]
                dp[k][2] += dp[k+1][1] * 2
            else:
                dp[k][0] += dp[k+1][1]
                dp[k][1] += dp[k+1][1]
                dp[k][2] += dp[k+1][1]
        else:
            dp[k][2] += dp[k+1][2] * 3
        map(lambda x:x%mod, dp[k])
print(sum(dp[0]) % mod)

from functools import lru_cache

MOD = 10**9 + 7

@lru_cache(None)
def F(N):
  # (u,v) = (a^b,a+b), (a^b,a+b+1) という組の個数x,y. where v <= N
  if N == 0:
    return 1,1
  x,y = 0,0
  # (0,0) mod 2
  x1,y1 = F(N//2)
  x += x1
  y += x1
  # (0,1) mod 2
  x2,y2 = F((N-1)//2)
  x += x2
  y += y2
  # (1,1) mod 2
  if N > 1:
    x3,y3 = F((N-2)//2)
    x += y3
    y += y3

  return x%MOD,y%MOD
  
answer = F(int(input()))[0]
           
print(answer)
  
  


def xor_sum(N: int)->int:
    MOD = 10**9 + 7

    digits = len(bin(N)) - 2

    dp = [[0] * 3 for _ in range(digits+1)]
    dp[0][0] = 1

    for i in range(digits):
        if N >> (digits - 1 - i) & 1:
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = (dp[i][0] + dp[i][1]) % MOD
            dp[i+1][2] = (dp[i][1] * 2 + dp[i][2] * 3) % MOD
        else:
            dp[i+1][0] = (dp[i][0] + dp[i][1]) % MOD
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = (dp[i][1] + dp[i][2] * 3) % MOD

    return sum(dp[digits]) % MOD


def __starting_point():
    N = int(input())
    ans = xor_sum(N)
    print(ans)

__starting_point()

# coding: utf-8
# Your code here!
odd={0:1}
even={0:1,1:3}
M=10**9+7
def memo(N):
    if N ==0:
        return 1
    if N==1:
        return 2
    return (memoodd((N-1)//2)+memoeven(N//2))%M


def memoodd(N):
    if N in odd:
        return odd[N]
#    a=memoodd((N-1)//2)
#    b=memoeven(N//2)
    odd[N] = memo(N)
    return odd[N]

def memoeven(N):
    if N in even:
        return even[N]
#    a=memoodd((N-1)//2)
#    b=memoeven(N//2)
#    c=memoodd((N-2)//2)
#    d=memoeven((N-1)//2)
#    return a+b+c+d
    even[N] = (memo(N)+memo(N-1))%M
    return even[N]

n=int(input())

print((memo(n)))


n=int(input())
m=10**9+7
s=bin(n)[2:]
t=[[0,0,0]for i in range(len(s)+1)]
t[0][0]=1
for i in range(1,len(s)+1):
    if s[i-1]=="0":
        t[i][0]=t[i-1][0]+t[i-1][1]
        t[i][1]=t[i-1][1]
        t[i][2]=t[i-1][1]+t[i-1][2]*3
    else:
        t[i][0]=t[i-1][0]
        t[i][1]=t[i-1][0]+t[i-1][1]
        t[i][2]=t[i-1][2]*3+t[i-1][1]*2
    for j in range(3):
        t[i][j]%=m
print(sum(t[-1])%m)

import sys
sys.setrecursionlimit(10**9)

N=int(input())
mod=10**9+7
DP=dict()
DP[(0,0)]=1#a+b,a^b
DP[(1,0)]=1
DP[(1,1)]=2

def ans(S,X):
    #print(S,X)
    if DP.get((S,X))!=None:
        return DP[(S,X)]
    if S==0:
        return 1
    #if X>S:
    #    return ans(S,S)
    

    DP[(S,X)]=(ans(S//2,X//2)+ans((S-1)//2,(X-1)//2)+ans((S-2)//2,(X-2)//2))%mod
    #一番下の桁をみて、bitが0,0の場合,1,0の場合,1,1の場合.
    #三つ目の場合は本来ans((S-2)//2,X//2)だが,今回扱うのはS=Xのときで,X>Sのときは0になるので,ans((S-2)//2,(X-2)//2)で良いはず.
    return DP[(S,X)]

print((ans(N,N)))


# -*- 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 list(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))


from functools import*
@lru_cache(None)
def d(n):x=n//2;return n+1 if n<2 else d(x)+d(~-x)+d(n+~x)
print(d(int(input()))%(10**9+7))

import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())


MOD = 10**9+7

n = ni()
n_bit = len(bin(n)[2:])

dp = [[0]*4 for _ in range(n_bit+1)]
dp[0][0] = 1

for bit in range(n_bit):
    digit = int(bin(n)[2+bit:2+bit+1])
    
    if digit:
        dp[bit+1][0] = (dp[bit][0]) % MOD
        dp[bit+1][1] = (dp[bit][0] + dp[bit][1]) % MOD
        dp[bit+1][2] = (dp[bit][1]) % MOD
        dp[bit+1][3] = (dp[bit][1] + 3*dp[bit][2] + 3*dp[bit][3]) % MOD
        
    else:
        dp[bit+1][0] = (dp[bit][0] + dp[bit][1]) % MOD
        dp[bit+1][1] = (dp[bit][1]) % MOD
        dp[bit+1][2] = (dp[bit][1] + dp[bit][2]) % MOD
        dp[bit+1][3] = (2*dp[bit][2] + 3*dp[bit][3]) % MOD
        
print(sum(dp[n_bit]) % MOD)

from functools import*
@lru_cache(maxsize=None)
def d(n):x=n//2;return n+1 if n<2 else d(x)+d(~-x)+d(n+~x)
print(d(int(input()))%(10**9+7))