Problem:
 Score : 600 points    Problem Statement Given are integers L and R . Find the number, modulo 10^9 + 7 , of pairs of integers (x, y)  (L \leq x \leq y \leq R) such that the remainder when y is divided by x is equal to y \mbox{ XOR } x .   What is \mbox{ XOR } ?  The XOR of integers A and B , A \mbox{ XOR } B , is defined as follows:  When A \mbox{ XOR } B is written in base two, the digit in the 2^k 's place ( k \geq 0 ) is 1 if either A or B , but not both, has 1 in the 2^k 's place, and 0 otherwise.  For example, 3 \mbox{ XOR } 5 = 6 . (In base two: 011 \mbox{ XOR } 101 = 110 .)       Constraints  1 \leq L \leq R \leq 10^{18}         Input Input is given from Standard Input in the following format:  L  R       Output Print the number of pairs of integers (x, y)  (L \leq x \leq y \leq R) satisfying the condition, modulo 10^9 + 7 .        Sample Input 1 2 3      Sample Output 1 3  Three pairs satisfy the condition: (2, 2) , (2, 3) , and (3, 3) .       Sample Input 2 10 100      Sample Output 2 604       Sample Input 3 1 1000000000000000000      Sample Output 3 68038601  Be sure to compute the number modulo 10^9 + 7 .

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
input=lambda :sys.stdin.buffer.readline().rstrip()
class ModInt(object):
    __MOD=10**9+7

    def __init__(self,x):
        self.__x=x%self.__MOD

    def __repr__(self):
        return str(self.__x)

    def __add__(self,other):
        return ModInt(self.__x+other.__x) if isinstance(other,ModInt) else ModInt(self.__x+other)

    def __sub__(self,other):
        return ModInt(self.__x-other.__x) if isinstance(other,ModInt) else ModInt(self.__x-other)

    def __mul__(self,other):
        return ModInt(self.__x*other.__x) if isinstance(other,ModInt) else ModInt(self.__x*other)

    def __truediv__(self,other):
        return ModInt(self.__x*pow(other.__x,self.__MOD-2,self.__MOD)) if isinstance(other, ModInt) else ModInt(self.__x*pow(other, self.__MOD-2,self.__MOD))

    def __pow__(self,other):
        return ModInt(pow(self.__x,other.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(self.__x,other,self.__MOD))

    __radd__=__add__

    def __rsub__(self,other):
        return ModInt(other.__x-self.__x) if isinstance(other,ModInt) else ModInt(other-self.__x)

    __rmul__=__mul__

    def __rtruediv__(self,other):
        return ModInt(other.__x*pow(self.__x,self.__MOD-2,self.__MOD)) if isinstance(other,ModInt) else ModInt(other*pow(self.__x,self.__MOD-2,self.__MOD))

    def __rpow__(self,other):
        return ModInt(pow(other.__x,self.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(other,self.__x,self.__MOD))
def resolve():
    from itertools import product
    L,R=map(int,input().split())
    D=61
    dp=[[[[ModInt(0)]*2 for _ in range(2)] for _ in range(2)] for _ in range(D+1)]
    dp[D][0][0][0]=ModInt(1)
    for d in range(D-1,-1,-1):
        lb=L>>d&1; rb=R>>d&1
        for i,j,m,x,y in product([0,1],repeat=5):
            ni,nj,nm=i,j,m
            if(x>y): continue
            
            if(i==0 and lb>x): continue
            if(lb<x): ni=1
            
            if(j==0 and y>rb): continue
            if(y<rb): nj=1
            
            if(m==0 and x!=y): continue
            if(x==1 and y==1): nm=1
            dp[d][ni][nj][nm]+=dp[d+1][i][j][m];
    print(sum(dp[0][i][j][m] for i,j,m in product([0,1],repeat=3)))
resolve()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import lru_cache

MOD = 10**9 + 7

def Fsmall(L,R):
    return sum(y-x == x^y for x in range(L,R+1) for y in range(x,min(x+x-1,R)+1))

@lru_cache(None)
def F(L,R):
    
    if R-L < 10:
        return Fsmall(L,R)
    f = 0
    
    f += F((L+1)//2,R//2)
    
    
    f += F((L+1)//2,(R-1)//2)
    
    f += G(L//2,(R-1)//2)
    return f%MOD

def Gsmall(L,R):
    return sum(y-x == x^y for x in range(L,R+1) for y in range(x,min(x+x,R)+1))

@lru_cache(None)
def G(L,R):
    
    if R-L < 10:
        return Gsmall(L,R)
    f = 0
    
    f += G((L+1)//2,R//2)
    
    
    f += F((L+1)//2,(R-1)//2)
    
    f += G(L//2,(R-1)//2)
    return f%MOD

L,R = map(int,read().split())

answer = F(L,R)
print(answer)

Solution (Python):
from itertools import product

MOD = 10**9 + 7

L, R = map(int, input().split())

binR = bin(R+1)[2:]
maxD = len(binR)
binL = bin(L-1)[2:].zfill(maxD)

dp = [[[[0]*(2) for k in range(2)] for j in range(2)] for i in range(maxD+1)]
dp[0][0][0][0] = 1
for d, (Ld, Rd) in enumerate(zip(binL, binR)):
    Ld, Rd = int(Ld), int(Rd)
    for isLleX, isYleR, isNum in product(range(2), repeat=3):
        for x, y in [(0,0), (0,1), (1,1)]:
            if not isNum and (x, y) == (0, 1): continue
            if not isLleX and x < Ld: continue
            if not isYleR and y > Rd: continue
            isLleX2 = isLleX or x > Ld
            isYleR2 = isYleR or y < Rd
            isNum2 = isNum or y == 1
            dp[d+1][isLleX2][isYleR2][isNum2] += dp[d][isLleX][isYleR][isNum]
            dp[d+1][isLleX2][isYleR2][isNum2] %= MOD

print(dp[-1][1][1][1])

Solution (Python):
l, r = input().split()
l = int(l)
r = int(r)

dp = [[[-1 for k in range(2)] for j in range(2)] for i in range(64)]

def bbin(num):
    res = []
    while num:
        res.append(num % 2)
        num //= 2

    return res

numr = bbin(r)
numl = bbin(l)
while len(numl) < len(numr):
    numl.append(0)

def rec(pos, brr, brl):
    global numl, numr, dp
    if pos < 0:
        return 1

    if dp[pos][brr][brl] != -1:
        return dp[pos][brr][brl]

    res = 0
    if brr:
        if brl:
            res = 3 * rec(pos - 1, brr, brl)
        else:
            if numl[pos] == 1:
                res = rec(pos - 1, brr, brl)
            else:
                res += (2 * rec(pos - 1, brr, 0))
                res += rec(pos - 1, brr, 1)
    else:
        if numr[pos] == 1:
            if brl:
                res += (2 * rec(pos - 1, 0, brl))
                res += rec(pos - 1, 1, brl)
            else:
                if numl[pos] == 1:
                    res += rec(pos - 1, 0, brl)
                else:
                    res += rec(pos - 1, 0, 0)
                    res += rec(pos - 1, 0, 1)
                    res += rec(pos - 1, 1, 0)
        else:
            if brl:
                res += rec(pos - 1, 0, brl)
            elif numl[pos] == 0:
                res += rec(pos - 1, 0, 0)

    dp[pos][brr][brl] = res % (10**9 + 7)
    return dp[pos][brr][brl]

c = 0
for i in range(len(numl) - 1, -1, -1):
    if numl[i] == 1:
        c += rec(i - 1, 1 if i < len(numl) - 1 else 0, 0)
        break
    else:
        c += rec(i - 1, 1 if i < len(numl) - 1 else 0, 1)

print(c % (10**9 + 7))

Solution (Python):

LARGE = 10 ** 9 + 7






def f(pos, flag_x, flag_y, flag_z, memo, left, right):
    if pos == -1:
        return 1
    if memo[pos][flag_x][flag_y][flag_z] != -1:
        return memo[pos][flag_x][flag_y][flag_z]
    ret = 0
    
    if flag_x or left[pos] == '0':
        ret += f(pos - 1, flag_x, 1 if right[pos] == '1' else flag_y, flag_z, memo, left, right)
    
    if (flag_x or left[pos] == '0') and (flag_y or right[pos] == '1') and flag_z:
        ret += f(pos - 1, flag_x, flag_y, flag_z, memo, left, right)
    
    if flag_y or right[pos] == '1':
        ret += f(pos - 1, 1 if left[pos] == '0' else flag_x, flag_y, 1, memo, left, right)
    ret %= LARGE
    memo[pos][flag_x][flag_y][flag_z] = ret
    return ret


def solve_greed_f(L, R):

    res_g = 0

    for i in range(L, R + 1):
        for j in range(i, R + 1):
            if j % i == j ^ i:
                res_g += 1

    return res_g


def main():

    ll, rr = map(int, input().split())

    left = '{:060b}'.format(ll)[::-1]
    right = '{:060b}'.format(rr)[::-1]

    memo = [[[[-1 for m in range(2)] for k in range(2)] for j in range(2)] for i in range(60)]

    res = f(59, 0, 0, 0, memo, left, right)

    print(res)


if __name__ == "__main__":
    main()

Solution (Python):


from collections import deque, defaultdict
import itertools as ite
import sys
import math
import decimal

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

L_, R_ = map(int, raw_input().split())

ans = 0
for MSB in range(70):
    S = 2 ** MSB
    if S * 2 <= L_ or R_ < S:
        continue
    L, R = L_, R_
    if L <= S:
        L = S
    if 2 * S - 1 <= R:
        R = 2 * S - 1
    n1 = nL = nR = 0
    nLR = 1
    SL = SR = 1
    for i in range(MSB)[::-1]:
        flag1 = ((1 << i) & L != 0)
        flag2 = ((1 << i) & R != 0)
        SL *= 2
        SR *= 2
        SL += flag1
        SR += flag2
        n1 *= 3
        if flag1 and not flag2:
            nLR = 0
        if SR - SL >= 2:
            n1 += SR / 2 - SL / 2 - 1
            if not flag1:
                n1 += nL
            if flag2:
                n1 += nR
            if not flag1:
                nL *= 2
                nL += 1
            if flag2:
                nR *= 2
                nR += 1
            if not flag1 and flag2:
                nL += nLR
                nR += nLR
    if L == R:
        ans += 1
    else:
        ans += n1 + (SR - SL + 1) + nL + nR + nLR
print ans % MOD

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[l,r]=i2()
z=10**9+7
dp=[[[[0 for l in range(2)]for k in range(2)]for j in range(2)]for i in range(61)]
dp[60][0][0][0]=1
for n in range(60)[::-1]:
 lb=l>>n&1
 rb=r>>n&1
 for x in range(2):
  for y in range(2):
   for i in range(2):
    for j in range(2):
     for k in range(2):
      ni=i+0
      nj=j+0
      nk=k+0
      if x>y:
         continue
      if k==0 and x!=y:
         continue
      if x&y:
         nk=1
      if i==0 and x<lb:
         continue
      if  x>lb:
         ni=1
      if j==0 and y>rb:
         continue
      if y<rb:
         nj=1
      dp[n][ni][nj][nk]+=dp[n+1][i][j][k]
      dp[n][ni][nj][nk]%=z
print((dp[0][1][1][1]+dp[0][0][1][1]+dp[0][1][0][1]+dp[0][0][0][1])%z)

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

def count(L, R):
    res = 0
    for j in range(70):
        res = (res + subcount(j, L, R)) % mod
    return res

def subcount(j, L, R):
    if j >= L.bit_length():
        return 0
    dp = [[0]*4 for _ in range(70)]
    
    cnt = 0
    if R.bit_length() != j+1:
        cnt += 1
    if L.bit_length() != j+1:
        cnt += 2
    dp[j][cnt] = 1
    
    for i in range(j, 0, -1):
        yf = R & (1<<(i-1))
        xf = L & (1<<(i-1))
        
        d0 = dp[i][0]
        if yf and xf:
            dp[i-1][0] += d0
            dp[i-1][2] += d0
            dp[i-1][3] += d0
        elif yf:
            dp[i-1][0] += d0
            dp[i-1][1] += d0
        elif xf:
            dp[i-1][2] += d0
        else:
            dp[i-1][0] += d0
        
        d1 = dp[i][1]
        if xf:
            dp[i-1][1] += d1
            dp[i-1][3] += 2*d1
        else:
            dp[i-1][1] += 2*d1
        
        d2 = dp[i][2]
        if yf:
            dp[i-1][2] += 2*d2
            dp[i-1][3] += d2
        else:
            dp[i-1][2] += d2
        
        d3 = dp[i][3]
        dp[i-1][3] += 3*d3
        
        dp[i-1][0] %= mod
        dp[i-1][1] %= mod        
        dp[i-1][2] %= mod
        dp[i-1][3] %= mod
        
    return sum(dp[0][i] for i in range(4))

L, R = map(int, input().split())
print((count(R, R) - count(L-1, R))%mod)

Solution (Python):
L, R = map(int, input().split())

mod = 10 ** 9 + 7

dp = [[[0] * 2 for _ in range(2)] for _ in range(2)]
dp[0][0][0] = 1

for i in range(60, -1, -1) :
    lb, rb = (L >> i) & 1, (R >> i) & 1
    dp_ = [[[0] * 2 for _ in range(2)] for _ in range(2)]
    for lf in range(2) :
        for rf in range(2) :
            for msb in range(2) :
                for l in range(2) :
                    for r in range(2) :
                        nlf, nrf, nmsb = lf, rf, msb
                        if l > r : continue
                        if not msb and l != r : continue
                        if l and r :
                            nmsb = 1
                        if not lf and l < lb : continue
                        if l > lb :
                            nlf = 1
                        if not rf and r > rb : continue
                        if r < rb :
                            nrf = 1
                        dp_[nlf][nrf][nmsb] += dp[lf][rf][msb]
                        dp_[nlf][nrf][nmsb] %= mod
    dp = dp_
    
ret = 0
for i in range(2) :
    for j in range(2) :
        for k in range(2) :
            ret += dp[i][j][k]
            
print(ret % mod)

Solution (Python):
from itertools import product
L, R = map(int, input().split())
MOD = 10**9 + 7

dp = [[[0, 0] for _ in range(2)] for _ in range(2)]
pp = [[[0, 0] for _ in range(2)] for _ in range(2)]
dp[0][0][0] = 1
for d in range(60, -1, -1):
    pp, dp = dp, pp
    dp = [[[0, 0] for _ in range(2)] for _ in range(2)]
    lb = L>>d & 1
    rb = R>>d & 1
    if d == 1:
        pass
    ans = 0
    for lrs in product((0,1), repeat=3):
        l, r, s = lrs
        for xy in product((0,1), repeat=2):
            nl, nr, ns = l, r, s
            x, y = xy
            if x and not y:
                continue
            if not s and x != y:
                continue
            if x and y:
                ns = 1
            if not l and not x and lb:
                continue
            if x and not lb:
                nl = 1
            if not r and y and not rb:
                continue
            if not y and rb:
                nr = 1
            dp[nl][nr][ns] += pp[l][r][s]
            dp[nl][nr][ns] %= MOD

print(sum(dp[l][r][s] for l in (0,1) for r in (0,1) for s in (0,1)) % MOD)

Solution (Python):
L,R=map(int,input().split())
mod=10**9+7

DP_ini=[[[0 for i in range(2)] for j in range(2)] for k in range(64)]

import copy
ANS=0

for begin in range(64):
    DP=copy.deepcopy(DP_ini)

    if L<(1<<(begin+1)) and (1<<begin)<=R:

        if not(1<<begin <= L <  1<<(begin+1)) and not(1<<begin <= R <  1<<(begin+1)):
            DP[begin][0][0]=1

        elif 1<<begin <= L <  1<<(begin+1) and not(1<<begin <= R <  1<<(begin+1)):
            DP[begin][1][0]=1

        elif not(1<<begin <= L <  1<<(begin+1)) and 1<<begin <= R <  1<<(begin+1):
            DP[begin][0][1]=1

        else:
            DP[begin][1][1]=1

    for keta in range(begin-1,-1,-1):

        if L & (1<<keta)==0 and R & (1<<keta)==0:
            DP[keta][0][0]=DP[keta][0][0]+DP[keta+1][0][0]*3+DP[keta+1][0][1]*0+DP[keta+1][1][0]*1+DP[keta+1][1][1]*0
            DP[keta][0][1]=DP[keta][0][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*1+DP[keta+1][1][0]*0+DP[keta+1][1][1]*0
            DP[keta][1][0]=DP[keta][1][0]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*2+DP[keta+1][1][1]*0
            DP[keta][1][1]=DP[keta][1][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*0+DP[keta+1][1][1]*1

        elif L & (1<<keta)!=0 and R & (1<<keta)==0:
            DP[keta][0][0]=DP[keta][0][0]+DP[keta+1][0][0]*3+DP[keta+1][0][1]*0+DP[keta+1][1][0]*0+DP[keta+1][1][1]*0
            DP[keta][0][1]=DP[keta][0][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*1+DP[keta+1][1][0]*0+DP[keta+1][1][1]*0
            DP[keta][1][0]=DP[keta][1][0]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*1+DP[keta+1][1][1]*0
            DP[keta][1][1]=DP[keta][1][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*0+DP[keta+1][1][1]*0

        elif L & (1<<keta)==0 and R & (1<<keta)!=0:
            DP[keta][0][0]=DP[keta][0][0]+DP[keta+1][0][0]*3+DP[keta+1][0][1]*1+DP[keta+1][1][0]*1+DP[keta+1][1][1]*0
            DP[keta][0][1]=DP[keta][0][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*2+DP[keta+1][1][0]*0+DP[keta+1][1][1]*1
            DP[keta][1][0]=DP[keta][1][0]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*2+DP[keta+1][1][1]*1
            DP[keta][1][1]=DP[keta][1][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*0+DP[keta+1][1][1]*1
        else:
            DP[keta][0][0]=DP[keta][0][0]+DP[keta+1][0][0]*3+DP[keta+1][0][1]*1+DP[keta+1][1][0]*0+DP[keta+1][1][1]*0
            DP[keta][0][1]=DP[keta][0][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*2+DP[keta+1][1][0]*0+DP[keta+1][1][1]*0
            DP[keta][1][0]=DP[keta][1][0]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*1+DP[keta+1][1][1]*0
            DP[keta][1][1]=DP[keta][1][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*0+DP[keta+1][1][1]*1

    
    ANS+=sum(DP[0][0])+sum(DP[0][1])

print(ANS%mod)

Solution (Python):
import sys
import math

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    md = 10 ** 9 + 7
    l, r = map(int, input().split())
    n = int(math.log2(r)) + 1
    
    dp = [[[[0] * 2 for _ in range(2)] for __ in range(2)] for ___ in range(n + 1)]
    dp[0][0][0][0] = 1
    ans = 0
    for i in range(n):
        lk = l >> (n - 1 - i) & 1
        rk = r >> (n - 1 - i) & 1
        for t in range(2):
            for f in range(2):
                for g in range(2):
                    pre = dp[i][t][f][g]
                    for x, y in [(0, 0), (0, 1), (1, 1)]:
                        nt, nf, ng = t, f, g
                        if t == 0 and (x, y) == (0, 1): continue
                        if f == 0 and lk > x: continue
                        if g == 0 and y > rk: continue
                        if (x, y) == (1, 1): nt = 1
                        if lk == 0 and x == 1: nf = 1
                        if y == 0 and rk == 1: ng = 1
                        if i == n - 1:
                            ans = (ans + pre) % md
                        else:
                            dp[i + 1][nt][nf][ng] = (dp[i + 1][nt][nf][ng] + pre) % md
    print(ans)

main()

Solution (Python):
L, R = map(int, input().split())
MOD = 10 ** 9 + 7
l = '{:060b}'.format(L)[::-1] 
r = '{:060b}'.format(R)[::-1] 

memo = [[[[-1 for l in range(2)] for k in range(2)] for j in range(2)] for i in range(60)]


def f(pos, flagX, flagY, flagZ):
    if pos == -1:
        return 1
    if memo[pos][flagX][flagY][flagZ] != -1:
        return memo[pos][flagX][flagY][flagZ]
    ret = 0
    
    if flagX or l[pos] == '0':
        ret += f(pos - 1, flagX, 1 if r[pos] == '1' else flagY, flagZ)
    
    if (flagX or l[pos] == '0') and (flagY or r[pos] == '1') and flagZ:
        ret += f(pos - 1, flagX, flagY, flagZ)
    
    if flagY or r[pos] == '1':
        ret += f(pos - 1, 1 if l[pos] == '0' else flagX, flagY, 1)
    ret %= MOD
    memo[pos][flagX][flagY][flagZ] = ret
    return ret

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

Solution (Python):
L,R = map(int,input().split())

mod = 10**9+7

def f(L,R):
    if L>R : return 0
    R = bin(R)[2:]
    N = len(R)
    ret = f(L,int("0"+"1"*(N-1),2))
    L = bin(L)[2:]
    if len(L) != N : L = "1"+"0"*(N-1)
    for i in range(N):
        if R[i] == "0" : continue
        R2 = R[:i] + "0" + "?"*(N-i-1)
        if i==0: R2 = R
        for j in range(N):
            if j==0 : L2 = L
            elif L[j] == "1" : continue
            else : L2 = L[:j] + "1" + "?"*(N-j-1)

            tmp = 1
            for r,l in zip(R2,L2):
                if r=="0" and l=="1" : tmp *= 0 ; break
                elif r=="?" and l=="?" : tmp = tmp*3%mod
                elif r=="?" and l=="0" : tmp = tmp*2%mod
                elif r=="1" and l=="?" : tmp = tmp*2%mod
            ret += tmp
            ret %= mod
    return ret

print(f(L,R))

Solution (Python):
L,R = map(int,input().split())

mod = 10**9+7

def f(L,R):
    if L>R : return 0
    R = bin(R)[2:]
    N = len(R)
    ret = f(L,int("0"+"1"*(N-1),2))
    L = bin(L)[2:]
    if len(L) != N : L = "1"+"0"*(N-1)
    for i in range(N):
        if R[i] == "0" : continue
        R2 = R[:i] + "0" + "?"*(N-i-1)
        if i==0: R2 = R
        for j in range(N):
            if L[j] == "1" and j!=0 : continue
            L2 = L[:j] + "1" + "?"*(N-j-1)
            if j==0 : L2 = L
            tmp = 1
            for r,l in zip(R2,L2):
                if r=="0" and l=="1" : tmp *= 0 ; break
                elif r=="?" and l=="?" : tmp = tmp*3%mod
                elif r=="?" and l=="0" : tmp = tmp*2%mod
                elif r=="1" and l=="?" : tmp = tmp*2%mod
            ret += tmp
            ret %= mod
    return ret

print(f(L,R))

Solution (Python):
L,R = map(int,input().split())

mod = 10**9+7

def f(L,R):
    if L>R : return 0
    R = bin(R)[2:]
    N = len(R)
    ret = f(L,int("0"+"1"*(N-1),2))
    L = bin(L)[2:]
    if len(L) != N : L = "1"+"0"*(N-1)
    for i in range(N):
        if R[i] == "0" : continue
        R2 = R[:i] + "0" + "?"*(N-i-1)
        if i==0: R2 = R
        for j in range(N):
            if L[j] == "1" and j!=0 : continue
            L2 = L[:j] + "1" + "?"*(N-j-1)
            if j==0 : L2 = L
            if L2[0] == "0" : break
            tmp = 1
            for r,l in zip(R2[1:],L2[1:]):
                if r=="0" and l=="1" : tmp *= 0 ; break
                if r=="?" and l=="?" : tmp = tmp*3%mod
                if r=="?" and l=="0" : tmp = tmp*2%mod
                if r=="1" and l=="?" : tmp = tmp*2%mod
            ret += tmp
            ret %= mod
    return ret

print(f(L,R))

Solution (Python):
L,R = map(int,input().split())

mod = 10**9+7
m = 64 +1
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

def f(L,R):
    if L>R : return 0
    R = bin(R)[2:]
    N = len(R)
    ret = f(L,int("0"+"1"*(N-1),2))
    L = bin(L)[2:]
    if len(L) != N : L = "1"+"0"*(N-1)
    for i in range(N):
        if R[i] == "0" : continue
        R2 = R[:i] + "0" + "?"*(N-i-1)
        if i==0: R2 = R
        for j in range(N):
            if L[j] == "1" and j!=0 : continue
            L2 = L[:j] + "1" + "?"*(N-j-1)
            if j==0 : L2 = L
            if L2[0] == "0" : break
            tmp = 1
            for r,l in zip(R2[1:],L2[1:]):
                if r=="0" and l=="1" : tmp *= 0
                if r=="?" and l=="?" : tmp *= 3
                if r=="?" and l=="0" : tmp *= 2
                if r=="1" and l=="?" : tmp *= 2
                tmp %= mod
            ret += tmp
            ret %= mod
    return ret%mod

print(f(L,R))

Solution (Python):
L,R = map(int,input().split())

mod = 10**9+7
m = 64 +1
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

def f(L,R):
    if L>R : return 0
    R = bin(R)[2:]
    N = len(R)
    ret = f(L,int("0"+"1"*(N-1),2))
    L = bin(L)[2:]
    if len(L) != N : L = "1"+"0"*(N-1)
    for i in range(N):
        if R[i] == "0" : continue
        R2 = R[:i] + "0" + "?"*(N-i-1)
        if i==0: R2 = R
        for j in range(N):
            if L[j] == "1" and j!=0 : continue
            L2 = L[:j] + "1" + "?"*(N-j-1)
            if j==0 : L2 = L
            if L2[0] == "0" : break
            tmp = 1
            for r,l in zip(R2[1:],L2[1:]):
                if r=="0" and l=="1" : tmp *= 0
                if r=="?" and l=="?" : tmp *= 3
                if r=="?" and l=="0" : tmp *= 2
                if r=="1" and l=="?" : tmp *= 2
            ret += tmp
            ret %= mod
    return ret%mod

print(f(L,R))

Solution (Python):
import os
import os
import sys
from collections import defaultdict

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

L, R = list(map(int, sys.stdin.readline().split()))


def test(L, R):
    ans = 0
    cnt = defaultdict(int)
    for x in range(L, R + 1):
        for y in range(x, R + 1):
            if y % x == y ^ x:
                cnt[x + y % x] += 1
                ans += 1
    return ans


def solve(L, R):
    ret = L == 1
    for msb in range(R.bit_length()):
        r = min(R, (1 << msb + 1) - 1)
        l = max(L, (1 << msb))
        if l > r:
            continue
        
        
        dp = np.zeros((r.bit_length(), 2, 2), dtype=int)
        for d in reversed(range(r.bit_length() - 1)):
            dp[-1][0][0] = 1
            if r >> d & 1:
                if l >> d & 1:
                    
                    
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][0] += dp[d + 1][1][0]
                    dp[d][0][1] += dp[d + 1][0][1]
                    dp[d][0][0] += dp[d + 1][0][0]
                    
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][0][1] += dp[d + 1][0][1]
                    
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][1] += dp[d + 1][0][1]
                else:
                    
                    
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][1] += dp[d + 1][1][0]
                    dp[d][0][1] += dp[d + 1][0][1]
                    dp[d][0][1] += dp[d + 1][0][0]
                    
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][0] += dp[d + 1][1][0]
                    dp[d][0][1] += dp[d + 1][0][1]
                    dp[d][0][0] += dp[d + 1][0][0]
                    
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][0] += dp[d + 1][1][0]
                    dp[d][1][1] += dp[d + 1][0][1]
                    dp[d][1][0] += dp[d + 1][0][0]
            else:
                if l >> d & 1:
                    
                    
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][0] += dp[d + 1][1][0]
                    
                    dp[d][1][1] += dp[d + 1][1][1]
                    
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][0][1] += dp[d + 1][0][1]
                else:
                    
                    
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][1] += dp[d + 1][1][0]
                    
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][0] += dp[d + 1][1][0]
                    
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][0] += dp[d + 1][1][0]
                    dp[d][0][1] += dp[d + 1][0][1]
                    dp[d][0][0] += dp[d + 1][0][0]
            dp[d] %= MOD
        ret += dp[0].sum()
        ret %= MOD
    return int(ret)


print(solve(L, R))

Solution (Python):
L,R = map(int,input().split())

mod = 10**9+7
m = 64 +1
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

def f(N):
    if N==0:return 0
    S = bin(N)[2:]
    L = len(S)
    ret = pow(2,S.count("1")-1,mod)
    for i in range(L):
        if S[i] == "0" : continue
        c = S[:i].count("1")
        j = max(0,L-i-1)
        for k in range(j+1):
            if c+k == 0 : continue
            ret += pow(2,c+k-1,mod)*comb(j,k)
            ret %= mod
    return ret

def g(R,L):
    if L==0 : return 0
    Nr = len(bin(R))-2
    Nl = len(bin(L))-2
    if Nr!=Nl :
        R = int("1"*Nl,2)
        Nr = Nl
    ret = f(int("0"+"1"*(Nr-1),2))
    
    R = bin(R)[2:]
    L = bin(L)[2:]
    for i in range(Nr):
        if R[i] == "0": continue
        if i==0 : R2 = R
        else: R2 = R[:i] + "0" + "?"*(Nr-i-1)
        for j in range(Nl):
            if L[j] == "0" : continue
            if j==0 : L2 = L
            else: L2 = L[:j] + "0" + "?"*(Nl-j-1)
            tmp = 1
            for r,l in zip(R2,L2):
                if r==l=="?" : tmp *= 3
                if r=="?" and l=="0" : tmp *= 2
                if r=="1" and l=="?" : tmp *= 2
                if r=="0" and l=="1" : tmp *= 0
                tmp %= mod
            ret += tmp
    return ret

print((f(R)-g(R,L-1))%mod)

Solution (Python):
def f_coincidence(MOD=10 ** 9 + 7):
    
    from itertools import product
    L, R = [int(i) for i in input().split()]

    dp = [[[[0 for s in range(2)] for k in range(2)]
           for j in range(2)] for i in range(61)]
    dp[60][0][0][0] = 1

    for i in range(59, -1, -1):
        lb = (L >> i) & 1  
        rb = (R >> i) & 1

        r2 = range(2)
        for j, k, s in product(r2, r2, r2):
            pre = dp[i + 1][j][k][s]
            
            for xb, yb in product(r2, r2):
                
                if xb == 1 and yb == 0:
                    continue
                

                nj, nk, ns = j, k, s
                
                if s == 0 and xb != yb:
                    continue  
                if s == 0 and xb == 1 and yb == 1:
                    ns = 1  

                
                if j == 0 and xb == 0 and lb == 1:
                    
                    
                    continue
                if j == 0 and xb == 1 and lb == 0:
                    nj = 1  

                
                if k == 0 and yb == 1 and rb == 0:
                    continue  
                if k == 0 and yb == 0 and rb == 1:
                    nk = 1

                
                dp[i][nj][nk][ns] += pre
                dp[i][nj][nk][ns] %= MOD

    ans = sum([dp[0][j][k][s] for j in range(2) for k in range(2)
               for s in range(2)]) % MOD
    return ans

print(f_coincidence())

Solution (Python):
def count(lb, rb):
    assert lb[0] == '1'
    assert rb[0] == '1'
    assert len(lb) == len(rb)
    dp = [1, 0, 0, 0]
    for lc, rc in zip(lb[1:], rb[1:]):
        ndp = [dp[0], 0, 0, 0]
        if rc == '0':
            ndp[1] += dp[1]
            if lc == '1':
                ndp[0] = 0
        else:
            ndp[1] += dp[1] * 2
            ndp[2] += dp[1]
            if lc == '0':
                ndp[1] += dp[0]
                ndp[3] += dp[0]
        if lc == '0':
            ndp[2] += dp[3]
            ndp[3] += dp[3] * 2
        else:
            ndp[3] += dp[3]
        ndp[2] += dp[2] * 3
        dp = ndp
    return sum(dp)


l, r = map(int, input().split())
lb = bin(l)[2:]
rb = bin(r)[2:]
ld = len(lb)
rd = len(rb)
ans = 0
MOD = 10 ** 9 + 7
for d in range(ld, rd + 1):
    tlb = lb if d == ld else '1' + '0' * (d - 1)
    trb = rb if d == rd else '1' * d
    ans = (ans + count(tlb, trb)) % MOD
print(ans)