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

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

def main():
    N = int(input())
    """
    (u, v)での数え上げを(a, b)への数え上げにすり替えることができる。
    (a, b)->(u, v)の対応は単射ではないが、実は
        「a, bのどれかのビットが(0, 1), (1, 0)で入れ替わっているようなものを同一視」
    することでこの対応は単射になる。(すなわちa + b = c + d, a ^ b = c ^ dは
    a, bの各ビットを一部入れ替えたものがc, dになることに同値)

    なので問題は次のように言い変わる：
        「非負整数a, bでa + b <= Nなるものを数え上げよ。
        　ただしa, bの各ビットは(0, 0), (0, 1), (1, 1)の３パターンに限る。」
    これは桁DPをすれば良いが、単純に上の桁からやると繰り上げ処理が扱えない。

    そこでNよりどれだけ小さいかの情報もdpデーブルに持たせる。
        dp[i][j] = (上から0~i桁目まで見たとき値がN - jであるものの個数)
    これによる遷移はiに応じて異なるものの(jに-0, -2^i, -2^{i+1}のどれかが実行される)
    一応解ける。しかし計算量的にはまだ厳しい。

    そもそも計算量が大きい原因は遷移幅が大きすぎるから。そこでキーの持ち方を
        dp[i][j] = (上から0~i桁目まで見たとき(v >> i) = (N >> i) - j)
    と定める。こうすればNのiビット目とa, bのiビット目を見比べて上とほぼ同様に
    dp計算が可能でかつdpテーブルはだいぶ密になる。さらにdp[i + 1][j]でj >= 2の時は
    a, bのiビット目をどう取っても差が2^i以下に縮まることはないため遷移をまとめることができる。

    気持ちとしては上位ビットから考えるんだけど差分はmod 2^iで考えることで差分を0,1,2以上（繰り上がりケース）
    に限定して、(i+1)->iの遷移時に差分が増加するからそれをa, bのビットを選んで差分を抑制するか増大したまま
    放置するかを考えるイメージ。

    それにしても繰り上がりケースをまとめて考えていいのは数式的には明らかだけど、実際に遷移を考える際には
    妙に偶然感があって不思議な感じ。
    """
    n = bin(N)[2:]
    dp = [1, 1, 0]
    for i, c in enumerate(n):
        if i == 0: continue
        if c == '0':
            
            
            
            dp = [dp[0] + dp[1], dp[1], dp[1] + dp[2] * 3]
        else:
            
            
            
            dp = [dp[0], dp[0] + dp[1], dp[1] * 2 + dp[2] * 3]
        dp = [dp[0] % mod, dp[1] % mod, dp[2] % mod]
    print(sum(dp) % mod)



if __name__ == "__main__":
    main()

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

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

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

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

Solution (Python):
mod=10**9+7
def solve(n):
    if n==0:
        return 1
    res=0
    if n%2==1:
        temp=solve(n//2)
        res+=2*temp
        if n>=2:
            res+=temp-exact(n//2)
        return res%mod
    else:
        temp=solve(n//2)
        res+=temp
        res+=(temp-exact(n//2))*2
        return res%mod

def exact(n):
    if n==0:
        return 1
    m=n.bit_length()
    dp=[[0 for i in range(3)] for j in range(m)]
    dp[0][0]=1
    dp[0][1]=int(n%2==0)
    for i in range(1,m):
        for j in range(3):
            if j==0:
                if n>>i &1==1:
                    dp[i][j]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%mod
                else:
                    dp[i][j]=dp[i-1][0]
            elif j==1:
                if n>>i &1==1:
                    dp[i][j]=(dp[i-1][1]+dp[i-1][2])%mod
                else:
                    dp[i][j]=dp[i-1][0]
            elif j==2:
                if n>>i&1==1:
                    dp[i][j]=0
                else:
                    dp[i][j]=(dp[i-1][1]+dp[i-1][2])%mod
    return dp[-1][0]

N=int(input())
print(solve(N))

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

memo={0:1}
def solve(n):
    if n in memo:
        return memo[n]
    res=0
    if n%2==1:
        res+=2*solve(n//2)
        if n>=2:
            res+=solve(n//2-1)
        memo[n]=0
        memo[n]=res%mod
        return res%mod
    else:
        res+=solve(n//2)
        res+=solve((n-1)//2)*(1+(n>=2))
        memo[n]=0
        memo[n]=res%mod
        return res%mod

print(solve(int(input())))

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

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

Solution (Python):


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

Solution (Python):
import sys

in1 = sys.stdin.readlines()
N = int(in1[0])


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

Solution (Python):
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)

    def get(self, init=None):
        if self.v is None:
            return init
        else:
            return self.v


def main():
    N = format(int(input()), "b")
    D = len(str(N))
    dp = [[0 for _ in range(3)] for __ in range(D + 1)]

    dp[0][0] = 1
    for d in range(D):
        for k in range(3):
            for s in range(3):
                sd = 2 * s + int(N[d]) - k
                if sd > 2:
                    sd = 2
                if sd < 0:
                    continue
                dp[d + 1][sd] += dp[d][s]
                dp[d + 1][sd] %= mod

    print(sum(dp[D]) % mod)


if __name__ == "__main__":
    main()

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

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

Solution (Python):

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

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

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

Solution (Python):

"""

a,bの組み合わせから u,vを作っていく
a,bが違うのに u,vが同じになるパターンはbit入れ替えのみ？

a1 ^ b1 == a2 ^ b2 とする
bit入れ替えでなく, 左右のabが等しくないとき、 00 と 11になっている
和にすると片方が片方より 2**[桁+1]大きい
→各桁について 2,4,8,16…の差が生まれるが、これらが相殺されることは無い。

よってabの各桁の組み合わせが (0,0)(0,1)(1,1)のどれかだけ調べればよい
u <= vより、vの条件だけ考えていく。


現時点でのNとの差が
0 * 2**(d+1) → (0,0)のみ設置可能
1 * 2**(d+1) → (0,0)(0,1)のみ設置可能
                (0,0) → 差は2 * (2**d)
2 *

(1,1)が来ると繰り上がってしまう。→ 2**(d+1)増える

dp[桁][乖離度]
"""
mod = 10**9+7
N = int(input())

NB = format(N,"b")

dp = [ [0]*3 for i in range(len(NB)) ]

dp[0][0] = 1
dp[0][1] = 1

for i in range(len(NB) - 1):

    if NB[i+1] == "0":
        
        dp[i+1][0] += dp[i][0]
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] += dp[i][2]

        
        
        dp[i+1][1] += dp[i][1]
        dp[i+1][2] += dp[i][2]

        
        dp[i+1][0] += dp[i][1]
        dp[i+1][2] += dp[i][2]

    else:
        
        
        dp[i+1][1] += dp[i][0]
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] += dp[i][2]

        
        dp[i+1][0] += dp[i][0]
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] += dp[i][2]

        
        
        dp[i+1][1] += dp[i][1]
        dp[i+1][2] += dp[i][2]

    dp[i+1][0] %= mod
    dp[i+1][1] %= mod
    dp[i+1][2] %= mod

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

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

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = float('INF')
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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 = 1000000007


n = I()
dp = [[0] * 3 for _ in range(62)]
dp[0][0] = 1
for i in range(61):
    zero, one, two = dp[i]
    if n >> (60 - i) & 1:
        zero, one, two = zero, zero + one, 2 * one + 3 * two
    else:
        zero, one, two = zero + one, one, one + 3 * two
    dp[i + 1] = [zero % mod, one % mod, two % mod]


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

Solution (Python):
N = int(input())
mod = 10**9+7
N = '{:060b}'.format(N)[::-1]

dp = [[[[-1 for _ in range(3)] for _ in range(2)] for _ in range(2)] for _ in range(60)]

def f(n,a,b,c):
    if n==-1:
        return 1
    if dp[n][a][b][c]!=-1:
        return dp[n][a][b][c]
    if b:
        res = f(n-1,1,1,2)+f(n-1,1,1,1)+f(n-1,1,1,0)
    else:
        if not a:
            if N[n]=='0':
                res = f(n-1,0,0,0)
            else:
                res = f(n-1,1,0,0)+f(n-1,0,0,1)
        else:
            if N[n]=='0':
                res = f(n-1,0,0,2)+f(n-1,1,0,1)+f(n-1,1,1,0)
            else:
                res = f(n-1,1,0,2)+f(n-1,1,1,1)+f(n-1,1,1,0)
    res %= mod
    dp[n][a][b][c] = res
    return res

ans = f(59,0,0,0)
print(ans)

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

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
from itertools import product
def resolve():
    n=int(input())
    dp=[1,0,0]
    for d in range(60,-1,-1):
        ndp=[0]*3
        nd=(n>>d)&1
        for s,ad,bd in product(range(3),range(2),range(2)):
            if(ad>bd): continue
            ns=min(2,2*s+nd-(ad+bd))
            if(ns<0): continue
            ndp[ns]+=dp[s]
            ndp[ns]%=MOD
        dp=ndp
    print(sum(dp)%MOD)    
resolve()

Solution (Python):

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)

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

n = int(input())
k = n.bit_length()

DP = [[0]*3 for i in range(k+1)]
DP[0][2] = 1
bit = [int(i) for i in bin(n)[2:]]
for i in range(k):
    DP[i+1][0] = 3*DP[i][0]
    if bit[i]:
        DP[i+1][1] += DP[i][1]
        DP[i+1][0] += 2*DP[i][1]
        DP[i+1][1] += DP[i][2]
        DP[i+1][2] += DP[i][2]
    else:
        DP[i+1][2] += DP[i][1]
        DP[i+1][1] += DP[i][1]
        DP[i+1][0] += DP[i][1]
        DP[i+1][2] += DP[i][2]

    for j in range(3):
        DP[i+1][j] %= mod

print(sum(DP[-1])%mod)

Solution (Python):


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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a = LS()
    if a[1][0] == "+":
        print(int("".join(a[0])) + int("".join(a[2])))
    else:
        print(int("".join(a[0])) - int("".join(a[2])))
    return


def B():
    _ = II()
    t = LI()
    tsum = sum(t)
    for _ in range(II()):
        p, x = LI()
        print(tsum - t[p - 1] + x)
    return


def C():
    n = II()
    a = LI()
    d = defaultdict(int)
    ans = 1
    if n & 1:
        for i in a:
            if i & 1:
                print(0)
                return
            d[i] += 1
        for a, b in d.items():
            if a:
                if b == 2:
                    ans *= 2
                    ans %= mod
                    continue
                print(0)
                return
            if b == 1:
                continue
            print(0)
            return
    else:
        for i in a:
            if i & 1:
                d[i] += 1
                continue
            print(0)
            return
        for a, b in d.items():
            if b == 2:
                ans *= 2
                ans %= mod
                continue
            print(0)
            return
    print(ans)
            
        
    return


def D():
    n = II()
    binmax = len(bin(n)) - 2
    dp = [[0] * 3 for i in range(binmax + 1)]
    dp[0][0] = 1
    for i in range(binmax):
        if (n >> binmax - 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] = (2 * dp[i][1] + 3 * dp[i][2]) % 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] + 3 * dp[i][2]) % mod

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

    return



if __name__ == '__main__':
    D()

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

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a = LS()
    if a[1][0] == "+":
        print(int("".join(a[0])) + int("".join(a[2])))
    else:
        print(int("".join(a[0])) - int("".join(a[2])))
    return


def B():
    _ = II()
    t = LI()
    tsum = sum(t)
    for _ in range(II()):
        p, x = LI()
        print(tsum - t[p - 1] + x)
    return


def C():
    n = II()
    a = LI()
    d = defaultdict(int)
    ans = 1
    if n & 1:
        for i in a:
            if i & 1:
                print(0)
                return
            d[i] += 1
        for a, b in d.items():
            if a:
                if b == 2:
                    ans *= 2
                    ans %= mod
                    continue
                print(0)
                return
            if b == 1:
                continue
            print(0)
            return
    else:
        for i in a:
            if i & 1:
                d[i] += 1
                continue
            print(0)
            return
        for a, b in d.items():
            if b == 2:
                ans *= 2
                ans %= mod
                continue
            print(0)
            return
    print(ans)
            
        
    return


def D():
    n = II()
    binmax = len(bin(n)) - 2
    dp = [[0] * 3 for i in range(binmax + 1)]
    dp[0][0] = 1
    for i in range(binmax):
        if (n >> binmax - 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] = (2 * dp[i][1] + 3 * dp[i][2]) % 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] + 3 * dp[i][2]) % mod
    print(sum(dp[binmax]) % mod)

    return



if __name__ == '__main__':
    D()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a = LS()
    if a[1][0] == "+":
        print(int("".join(a[0])) + int("".join(a[2])))
    else:
        print(int("".join(a[0])) - int("".join(a[2])))
    return


def B():
    _ = II()
    t = LI()
    tsum = sum(t)
    for _ in range(II()):
        p, x = LI()
        print(tsum - t[p - 1] + x)
    return


def C():
    n = II()
    a = LI()
    d = defaultdict(int)
    ans = 1
    if n & 1:
        for i in a:
            if i & 1:
                print(0)
                return
            d[i] += 1
        for a, b in d.items():
            if a:
                if b == 2:
                    ans *= 2
                    ans %= mod
                    continue
                print(0)
                return
            if b == 1:
                continue
            print(0)
            return
    else:
        for i in a:
            if i & 1:
                d[i] += 1
                continue
            print(0)
            return
        for a, b in d.items():
            if b == 2:
                ans *= 2
                ans %= mod
                continue
            print(0)
            return
    print(ans)
            
        
    return


def D():
    n = II()
    binmax = len(bin(n)) - 1
    dp = [[0] * 3 for i in range(binmax)]
    dp[0][0] = 1
    for i in range(binmax - 1):
        if n & (1 << (binmax - 2 - i)):
            dp[i + 1][0] = dp[i][0] % mod
            dp[i + 1][1] = (dp[i][0] + dp[i][1]) % mod
            dp[i + 1][2] = (2 * dp[i][1] + 3 * dp[i][2]) % 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] + 3 * dp[i][2]) % mod
    print(sum(dp[binmax - 1]) % mod)

    return



if __name__ == '__main__':
    D()

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

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

def func(N):
    S=str(bin(N))[2:]
    L=len(S)
    dp=[[0]*3 for i in range(L+1)]
    dp[0][0]=1
    for i in range(L):
        n=ord(S[i])-ord('0')
        for k in range(3):
            for s in range(3):
                if 2*s+n-k<0:
                    continue
                sd=min(2*s+n-k,2)
                dp[i+1][sd]+=dp[i][s]
                dp[i+1][sd]%=MOD
    return (dp[L][0]+dp[L][1]+dp[L][2])%MOD
print(func(N))

Solution (Python):
n = int(raw_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