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: MEDIUM_HARD

Starter code:

Solutions:
import sys
in1 = sys.stdin.readlines()
N = int(in1[0])
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 = 1000000000.0 + 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(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 = [[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)


import sys
input = sys.stdin.readline
N = int(input())
mod = 10 ** 9 + 7
binN = format(N, '061b')[::-1]
dp = [[0, 0, 0] for _ in range(61)]
dp[60][0] = 1
for i in range(59, -1, -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]
	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):
		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]
		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)


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


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


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())
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
N = int(sys.stdin.readline())
dp = [[0] * 3 for _ in range(N.bit_length())]
dp[-1][1] = 1
dp[-1][0] = 1
for i in reversed(list(range(N.bit_length() - 1))):
	if N >> i & 1:
		dp[i][1] += dp[i + 1][0]
		dp[i][2] += dp[i + 1][1]
		dp[i][2] += dp[i + 1][2]
		dp[i][0] += dp[i + 1][0]
		dp[i][2] += dp[i + 1][1]
		dp[i][2] += dp[i + 1][2]
		dp[i][1] += dp[i + 1][1]
		dp[i][2] += dp[i + 1][2]
	else:
		dp[i][0] += dp[i + 1][0]
		dp[i][2] += dp[i + 1][1]
		dp[i][2] += dp[i + 1][2]
		dp[i][1] += dp[i + 1][1]
		dp[i][2] += dp[i + 1][2]
		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))


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(1000000000.0) + 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}

	def f(k):
		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())
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):
	if N == 0:
		return (1, 1)
	(x, y) = (0, 0)
	(x1, y1) = F(N // 2)
	x += x1
	y += x1
	(x2, y2) = F((N - 1) // 2)
	x += x2
	y += y2
	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()


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
DP[1, 0] = 1
DP[1, 1] = 2

def ans(S, X):
	if DP.get((S, X)) != None:
		return DP[S, X]
	if S == 0:
		return 1
	DP[S, X] = (ans(S // 2, X // 2) + ans((S - 1) // 2, (X - 1) // 2) + ans((S - 2) // 2, (X - 2) // 2)) % mod
	return DP[S, X]
print(ans(N, N))


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 = [0] + list(map(int, N))
dp = list2d(61, 3, 0)
dp[60][0] = 1
for i in range(60, 0, -1):
	for j in range(3):
		for k in range(3):
			nxt = min(j * 2 + N[i] - k, 2)
			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)


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)