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):
N = int(input())
MOD = 10 ** 9 + 7

M = len(bin(N)) - 2
dp = [[0] * 3 for _ in range(M + 1)]
dp[0][0] = 1

for i in range(M) :
    if N >> (M - i - 1) & 1 :
        dp[i + 1][0] = dp[i][0] % MOD
        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] % MOD
        dp[i + 1][2] = (dp[i][1] + dp[i][2] * 3) % MOD
        
print(sum(dp[-1]) % MOD)

Solution (Python):
mod=10**9+7
n=int(input())
d=n.bit_length()
DP=[[0]*3 for _ in range(d+1)]
DP[0][0]=1
for i in range(d):
    if n>>(d-i-1)&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
print(sum(DP[-1])%mod)

Solution (Python):
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)

Solution (Python):

def read_input():
    n = int(input())
    return n


def mymod(x):
    return x % (10**9 + 7)


def submit():
    N = read_input()
    N = list(map(int, list(bin(N)[2:])))

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

    for i in range(len(N) - 1, -1, -1):
        for s in range(3):
            for k in range(3):
                new_s = 2 * s + N[len(N) - i - 1] - k
                if new_s < 0:
                    continue
                if new_s > 2:
                    new_s = 2
                dp[i][new_s] += dp[i + 1][s]
            dp[i][0] = mymod(dp[i][0])
            dp[i][1] = mymod(dp[i][1])
            dp[i][2] = mymod(dp[i][2])

    print(mymod((dp[0][0] + dp[0][1] + dp[0][2])))


if __name__ == '__main__':
    submit()

Solution (Python):
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


if __name__ == "__main__":
    N = int(input())
    ans = xor_sum(N)
    print(ans)

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)])

Solution (Python):
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))

Solution (Python):
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))

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

Solution (Python):
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)

Solution (Python):


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

Solution (Python):


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

Solution (Python):


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

Solution (Python):
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])

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
N=input()

memo={}
memo[0]=1
memo[1]=2

def func(N):
	if N in memo:
		return memo[N]
	result= ( func(N/2)+func((N-1)/2)+func(N/2-1) )% (10**9+7)
	
	memo[N]=result
	return result

print func(N)

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
N = int(input())
dp = [[0] * 3 for i in range(100)]

MOD = int(1e9+7)
maxBit = 70
while not (N >> maxBit):
    maxBit -= 1

dp[maxBit][0] = 1
dp[maxBit][1] = 1
for i in range(maxBit-1, -1, -1):
    for j in range(3):
        bit = (N >> i) & 1
        for k in range(3):
            nj = 2 * j + bit - k
            if nj < 0:
                continue
            nj = min((nj, 2))
            dp[i][nj] += dp[i+1][j]
            dp[i][nj] %= MOD

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

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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))