Problem:
 Score : 600 points    Problem 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 .      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 1 3      Sample Output 1 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 .）         Sample Input 2 1422      Sample Output 2 52277       Sample Input 3 1000000000000000000      Sample Output 3 787014179

Solution (Python):
mod = 10**9+7
n = int(input())
def nth_bit(d):
    return (n>>d)&1

dp = [[0,0,0] for _ in range(61)]
dp[-1][0] = 1
for d in range(59,-1,-1):
    for s in range(3):
        for k in range(3):
            s2 = min(2,2*s+nth_bit(d)-k)
            if s2>=0:
                dp[d][s2] += dp[d+1][s]
ans = sum(dp[0])%mod
print(ans)

Solution (Python):
n = int(input())
mod = 10**9 + 7

n_bit = []
x = n
while(x>0):
    n_bit.append(x%2)
    x //= 2
n_bit = n_bit[::-1]

n_len = len(n_bit)

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

for i,bi in enumerate(n_bit):
    if(bi == 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
    dp[i+1][0] %= mod
    dp[i+1][1] %= mod
    dp[i+1][2] %= mod

ans = sum(dp[-1]) % mod
print(ans)

Solution (Python):
n=int(input())
d=dict()
def get(n):
    if(n==1):return 1
    if(n==0):return 0
    if(n in d.keys()):return d[n]
    if(n%2==0):
        d[n]=2*get(n//2)+get(n//2-1)
    else:
        d[n]=2*get(n//2)+get(n//2+1)
    d[n]%=(10**9+7)
    return d[n]
def check(u,v,n):
    for a in range(n+1):
        b=u ^ a
        if(a+b==v):
            return 1
    return 0






print(get(n+1))

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int,read().split())

d = {}


"""
res = [[0]*100 for _ in range(100)]
for i in range(128):
    for j in range(128):
        u = i^j
        v = i+j
        if u<100 and v<100: res[u][v] = 1

x = 0
for i in range(n+1):
    for j in range(n+1):
        x += res[i][j]

for i in res[:10]:
    print(i[:10])

for i in range(100):
    for j in range(1,100):
        res[i][j] += res[i][j-1]
for i in range(1,100):
    for j in range(100):
        res[i][j] += res[i-1][j]



"""



def f(n,m):
    if (n,m) in d: return d[(n,m)]
    if n<0 or m<0:
        return 0
    if n==0:
        return max(1+n//2,1+m//2)
    if m==0:
        return 1

    nn = n>>1 if n&1 else (n>>1)-1
    mm = m>>1 if m&1 else (m>>1)-1
    
    
    
    v =  f(nn,mm) + f(n>>1,m>>1) + f(n>>1,(m>>1)-1)
    d[(n,m)] = v
    
    return v

ans = f(n,n)
print(ans%(10**9+7))

Solution (Python):
n=int(input())
mod=10**9+7
bt=bin(n)[2:]
k=len(bt)
dp=[[0]*2 for i in range(k+1)]
dp[0][0]=1
dp[0][1]=1
for i in range(k):
  j=int(bt[k-i-1])
  a,b,c=[(1,0,0),(1,1,0)][j]
  d,e,f=[(1,1,1),(0,1,2)][j]
  dp[i+1][0]=(a*dp[i][0]+b*dp[i][1]+c*(3**i))%mod
  dp[i+1][1]=(d*dp[i][0]+e*dp[i][1]+f*(3**i))%mod
print(dp[k][0])

Solution (Python):
import sys
from collections import Counter
readline = sys.stdin.readline
MOD = 10**9+7
N = int(readline())

CC = Counter()
CC[0] = 1
CC[1] = 2
def calc(x):
    res = 0
    if CC[x]:
        res = CC[x]
    elif x == 1:
        res = 2
    elif x%2 == 0:
        res = 2*calc(x//2-1) + calc(x//2)
    else:
        res = 2*calc(x//2) + calc(x//2-1)
    CC[x] = res%MOD
    return res%MOD
print(calc(N))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n  = bin(I())[2:]
dp0, dp1, dp2 = 1, 0, 0
for d in n:
    if d == '1':
        dp0, dp1, dp2 = dp0 % mod, (dp0 + dp1) % mod, (dp1 * 2 + dp2 * 3) % mod
    else:
        dp0, dp1, dp2 = (dp0 + dp1) % mod, dp1 % mod, (dp1 + dp2 * 3) % mod



print((dp0 + dp1 + dp2) % mod)

Solution (Python):
tg = 0
ls = 1
md = 2
MOD = 10**9+7
n = int(input())
l = n.bit_length()

dp = [[[0] * l for _ in range(3)] for i in range(2)]
for i in range(l):
    if i == 0:
        
        dp[tg][tg][0] = 1
        
        dp[ls][md][0] = 1
        continue
    
    if n & (1 << l - i - 1):
        
        dp[tg][tg][i] += dp[tg][tg][i-1]
        dp[ls][ls][i] += dp[ls][md][i-1]
        dp[ls][tg][i] += dp[ls][tg][i-1]
        dp[ls][ls][i] += dp[ls][ls][i-1]
        
        dp[ls][md][i] += dp[tg][tg][i-1]
        dp[ls][ls][i] += dp[ls][md][i-1]
        dp[ls][md][i] += dp[ls][tg][i-1]
        dp[ls][ls][i] += dp[ls][ls][i-1]
        
        dp[ls][md][i] += dp[ls][md][i-1]
        dp[ls][ls][i] += dp[ls][ls][i-1]
    
    else:
        
        dp[ls][ls][i] += dp[ls][ls][i-1]
        dp[ls][md][i] += dp[ls][md][i-1]
        
        dp[tg][tg][i] += dp[tg][tg][i-1]
        dp[ls][ls][i] += dp[ls][md][i-1]
        dp[ls][ls][i] += dp[ls][ls][i-1]
        dp[ls][tg][i] += dp[ls][tg][i-1]
        
        dp[ls][tg][i] += dp[ls][md][i-1]
        dp[ls][ls][i] += dp[ls][ls][i-1]
    for xp in dp:
        for pp in xp:
            pp[i] %= MOD

ans = 0
for xp in dp:
    for pp in xp:
        ans += pp[-1]
        ans %= MOD
print(ans)

Solution (Python):
n = int(input())
b = bin(n)[2:]
MOD = 10 ** 9 + 7

dp1, dp2, dp3 = 1, 0, 0

for d in b:
    if d == '1':
        dp1, dp2, dp3 = dp1 % MOD, (dp1 + dp2) % MOD, (dp2 * 2 + dp3 * 3) % MOD
    else:
        dp1, dp2, dp3 = (dp1 + dp2) % MOD, dp2, (dp2 + dp3 * 3) % MOD

print((dp1 + dp2 + dp3) % MOD)

Solution (Python):


N = int(input())
binN = format(N, "b").zfill(60)
mod = 7 + 10 ** 9

DP = [[0, 0, 0] for _ in range(60)]
if binN[0] == "0":
    DP[0] = [1, 0, 0]
else:
    DP[0] = [1, 1, 0]

for i in range(1, 60):   
    if binN[i] == "0":
        DP[i][0] = (DP[i-1][0] + DP[i-1][1]) % mod
        DP[i][1] = DP[i-1][1]
        DP[i][2] = (DP[i-1][2] * 3 + DP[i-1][1]) % mod
    else:
        DP[i][0] = DP[i-1][0]
        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
print(sum(DP[-1]) % mod)

Solution (Python):
N = int(input())
binN = format(N, "b").zfill(60)
mod = 7 + 10 ** 9

DP = [[0, 0, 0] for _ in range(60)]
if binN[0] == "0":
    DP[0] = [1, 0, 0]
else:
    DP[0] = [1, 1, 0]

for i in range(1, 60):   
    if binN[i] == "0":
        DP[i][0] = (DP[i-1][0] + DP[i-1][1]) % mod
        DP[i][1] = DP[i-1][1]
        DP[i][2] = (DP[i-1][2] * 3 + DP[i-1][1]) % mod
    else:
        DP[i][0] = DP[i-1][0]
        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
print(sum(DP[-1]) % mod)

Solution (Python):
MOD = 10**9 + 7
n = int(input())
dp = [[0 for _ in range(3)] for _ in range(61)]
dp[60][0] = 1
for i in range(59, -1, -1):
	if (n>>i)&1 == 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(sum(dp[0])%MOD)

Solution (Python):


from copy import deepcopy

MOD = 10 ** 9 + 7
IMAX = 200
JMAX = 2

def dp(n):
    dp = [0 for j in range(JMAX + 1)]
    dp[0] = 1
    for i in reversed(range(IMAX + 1)):
        pre = deepcopy(dp)
        dp[2] += pre[1]
        dp[2] += 2 * pre[2]
        d = ((1 << i) & n) >> i
        if d:
            dp[1] += pre[0]
            dp[2] += pre[1]
        else:
            dp[0] += pre[1]
        dp = take_mod(dp)
    return sum(dp) % MOD

def take_mod(dp):
    res = [x % MOD for x in dp]
    return res

def main():
    n = int(input())
    print(dp(n))

main()

Solution (Python):
N= int(input())
bit = bin(N)[2:]
k = len(bit)
dp = [[0] * 2 for i in range(len(bit) + 1)]
dp[0][0] = 1
dp[0][1] = 1
for i in range(k):
	j = int(bit[k-i-1])
	a,b,c = [(1,0,0),(1,1,0)][j]
	d,e,f = [(1, 1, 1),(0, 1, 2)][j]
	dp[i+1][0] = (a * dp[i][0] + b * dp[i][1] + c * 3**i) % 1000000007
	dp[i+1][1] = d * dp[i][0] + e * dp[i][1] + f * 3**i % 1000000007

print(dp[k][0])

Solution (Python):
MOD = 10 ** 9 + 7

N = int(input())

binN = list(map(int, bin(N)[2:]))
dp = [[0] * 3 for _ in range(len(binN) + 1)]
dp[0][0] = 1
for i, Ni in enumerate(binN):
    dp[i + 1][0] += dp[i][0] * 1
    dp[i + 1][1] += dp[i][0] * Ni
    dp[i + 1][0] += dp[i][1] * (1 - Ni)
    dp[i + 1][1] += dp[i][1] * 1
    dp[i + 1][2] += dp[i][1] * (1 + Ni)
    dp[i + 1][2] += dp[i][2] * 3
    dp[i + 1][0] %= MOD
    dp[i + 1][1] %= MOD
    dp[i + 1][2] %= MOD

print(sum(dp[-1]) % MOD)

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

n = input()
n = bin(n)[2:]

def func(dig, val1, val2):
    for i in range(dig):
        v1 = val1 * 2 + val2
        v2 = val2 * 2 + val1
        val1, val2 = v1, v2
    return val2

ans = 0
val1 = 0
val2 = 1
for i in range(len(n)):
    if n[i] == '1':
        ans += func(len(n) - i - 1, val1, val1 + val2)
        val1 = val1 + val2
    else:
        val2 = val1 + val2
print (ans + val2) % (10 ** 9 + 7)

Solution (Python):
def Dp(x, hl, islim):
    if x == len(digit):
        return hl == 0
    if f[x][hl][islim]:
        return f[x][hl][islim]
    ans = 0
    mx = int(digit[x]) if islim else 1
    for i in range(mx + 1):
        ans += Dp(x + 1, hl, islim and i == mx)
        if hl != i:
            ans += Dp(x + 1, not hl, islim and i == mx)
    ans %= p
    f[x][hl][islim] = ans
    return ans

p = 10**9 + 7
digit = bin(int(input()))[2:]
f = [[[0, 0], [0, 0]] for i in range(len(digit))]
print(Dp(0, 0, 1))

Solution (Python):
N = input()
MOD = 10**9+7

memo = {0: 1, 1: 2}
def S(k):
    if k in memo:
        return memo[k]
    if k % 2 == 1:
        result = (2*S(k/2) + S(k/2-1)) % MOD
    else:
        result = (S(k/2) + 2*S(k/2-1)) % MOD
    memo[k] = result
    return result
print S(N)

Solution (Python):
MOD = 10**9+7
d1 = {0: 1}
d2 = {0: 1, 1: 2}
def f(k):
    if k in d1:return d1[k]
    d1[k] = f(k/2) + (k%2<1 and f(k/2-1))
    return d1[k]
def s(k):
    if k in d2:return d2[k]
    d2[k] = (f(k) + s(k-1) if k%2 else s(k/2) + 2*s(k/2-1)) % MOD
    return d2[k]
print s(input())