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):
m=10**9+7
l,r=map(int,input().split())
dp=[[[[0 for _ in range(2)] for _ in range(2)] for _ in range(2)] for _ in range(61)]

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

for i in reversed(range(60)):
  lb=l>>i&1
  rb=r>>i&1
  for j in range(2):
    for k in range(2):
      for s in range(2):
        pre=dp[i+1][j][k][s]
        for x,y in [(0,0),(0,1),(1,1)]: 
          nj,nk,ns=j,k,s
          
          if (s==0 and x==0 and y==1): continue; 
          if (s==0 and x&y): ns=1;
          
          if (j==0 and lb==1 and x==0): continue; 
          if (j==0 and lb==0 and x==1): nj=1;
          
          if (k==0 and rb==0 and y==1): continue; 
          if (k==0 and rb==1 and y==0): nk=1;           
            
          dp[i][nj][nk][ns]+=pre
          dp[i][nj][nk][ns]%=m    
                  
ans=0             
for j in range(2):
  for k in range(2):
    ans+=dp[0][j][k][1]
    ans%=m
print(ans)

Solution (Python):
L, R = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7
for d in range(62):  
    
    
    l = max(1<<d, L)
    r = min((2<<d)-1, R)
    if l > r:
        continue
    dp_small = [0] * (d+2)
    dp_ok = [0] * (d+2)
    dp_large = [0] * (d+2)
    dp_small_large = [0] * (d+2)
    dp_small_large[0] = 1
    for n in range(1, d+2):
        i = d-n+1
        dp_ok[n] = dp_ok[n-1] * 3 \
                 + (dp_small[n-1] if l>>i&1==0 else 0) \
                 + (dp_large[n-1] if r>>i&1 else 0)
        dp_small[n] = dp_small[n-1] * (1 if l>>i&1 else 2) \
                    + (dp_small_large[n-1] if l>>i&1 < r>>i&1 else 0)
        dp_large[n] = dp_large[n-1] * (2 if r>>i&1 else 1) \
                    + (dp_small_large[n-1] if l>>i&1 < r>>i&1 else 0)
        dp_small_large[n] = dp_small_large[n-1] if l>>i&1 <= r>>i&1 else 0
    a = dp_ok[d+1] + dp_large[d+1] + dp_small[d+1] + dp_small_large[d+1]
    ans += a
    
    
    
    
    
    
print(ans % mod)

Solution (Python):
L, R = map(int, input().split())
dp = [[[[0]*2 for _ in range(2)] for _ in range(2)] for _ in range(65)]
dp[0][0][0][0] = 1
MOD = 10**9+7

for i in range(64):
    Li = (L>>(63-i))&1
    Ri = (R>>(63-i))&1
    
    for j in range(2):
        for k in range(2):
            for l in range(2):
                for x in (range(2) if j else range(Li, 2)):
                    for y in range(2 if k else Ri+1):
                        if x==1 and y==0:
                            continue
                        
                        if l==0 and x==0 and y==1:
                            continue
                        
                        dp[i+1][j|(x>Li)][k|(y<Ri)][l|(x==1 and y==1)] += dp[i][j][k][l]
                        dp[i+1][j|(x>Li)][k|(y<Ri)][l|(x==1 and y==1)] %= MOD

ans = 0

for i in range(2):
    for j in range(2):
        for k in range(2):
            ans += dp[-1][i][j][k]
            ans %= MOD

print(ans)

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

memo = {}
def solve(L, R):
    if (L, R) in memo:
        return memo[(L, R)]

    if L > R:
        res = 0
    elif L == 1:
        res = 1 + solve(2, R)
    else:
        res = (
            solve(L // 2, (R - 1) // 2) +
            solve((L + 1) // 2, R // 2) +
            solve((L + 1) // 2, (R - 1) // 2)
        )

    res %= mod
    memo[(L, R)] = res
    return res

L, R = map(int, input().split())
print(solve(L, R) % mod)

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


def countup(x, y):
    L1 = x.bit_length()
    x -= 1<<(L1-1)
    y -= 1<<(L1-1)
    L = x.bit_length()
    dp = [[[0, 0], [0, 0]] for _ in range(L+1)]
    
    dp[0][0][0] = 1
    for i in range(L):
        a = x&(1<<(L-1-i))
        b = y&(1<<(L-1-i))
        if a:
            if b:
                dp[i+1][0][0] = dp[i][0][0]
                dp[i+1][0][1] = 2*dp[i][0][1] % mod
                dp[i+1][1][0] = dp[i][1][0]
                dp[i+1][1][1] = (3*dp[i][1][1] + dp[i][0][1]) % mod
            else:
                dp[i+1][0][0] = dp[i][0][0]
                dp[i+1][0][1] = (dp[i][0][0] + 2*dp[i][0][1]) % mod
                dp[i+1][1][0] = (dp[i][0][0] + 2*dp[i][1][0]) % mod
                dp[i+1][1][1] = (3*dp[i][1][1] + dp[i][0][1] + dp[i][1][0]) % mod 
        else:
            if not b:
                dp[i+1][0][0] = dp[i][0][0]
                dp[i+1][0][1] = dp[i][0][1]
                dp[i+1][1][0] = 2*dp[i][1][0] % mod
                dp[i+1][1][1] = (3*dp[i][1][1] + dp[i][1][0]) % mod
            else:
                dp[i+1][0][1] = dp[i][0][1]
                dp[i+1][1][0] = dp[i][1][0]
                dp[i+1][1][1] = 3*dp[i][1][1] % mod
    return sum(dp[L][0]) + sum(dp[L][1]) % mod


def main():
    Left, Right = map(int, input().split())
    ans = 0
    while True:
        
        bl = Left.bit_length()
        br = Right.bit_length()
        if bl == br:
            ans = (ans + countup(Right, Left)) % mod
            break
        else:
            ans = (ans + countup(Right, (1<<(br-1)))) % mod
            Right = (1<<(br-1))-1
    
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def solve(L,R):
    n=R.bit_length()
    dp=[[0 for i in range(8)] for i in range(n)]
    if R&1==1 and L&1==1:
        dp[0][0]=1
        dp[0][1]=1
        dp[0][2]=2
        dp[0][3]=3
        dp[0][4]=1
        dp[0][5]=1
        dp[0][6]=2
        dp[0][7]=3
    elif R&1==1 and L&1==0:
        dp[0][0]=2
        dp[0][1]=3
        dp[0][2]=2
        dp[0][3]=3
        dp[0][4]=2
        dp[0][5]=3
        dp[0][6]=2
        dp[0][7]=3
    elif R&1==0 and L&1==1:
        dp[0][0]=0
        dp[0][1]=0
        dp[0][2]=1
        dp[0][3]=1
        dp[0][4]=1
        dp[0][5]=1
        dp[0][6]=2
        dp[0][7]=3
    else:
        dp[0][0]=1
        dp[0][1]=1
        dp[0][2]=1
        dp[0][3]=1
        dp[0][4]=2
        dp[0][5]=3
        dp[0][6]=2
        dp[0][7]=3
    for i in range(1,n):
        for j in range(8):
            if j==0:
                if R>>i &1==1 and L>>i &1==1:
                    dp[i][j]=dp[i-1][1]
                elif R>>i &1==1 and L>>i &1==0:
                    dp[i][j]=dp[i-1][4]+dp[i-1][3]
                elif R>>i&1 ==0 and L>>i&1 ==0:
                    dp[i][j]=dp[i-1][0]
            elif j==1:
                if R>>i &1==1 and L>>i &1==1:
                    dp[i][j]=dp[i-1][1]
                elif R>>i &1==1 and L>>i &1==0:
                    dp[i][j]=dp[i-1][5]+dp[i-1][3]+dp[i-1][1]
                elif R>>i&1==0 and L>>i&1==0:
                    dp[i][j]=dp[i-1][1]
            elif j==2:
                if R>>i&1==1:
                    dp[i][j]=dp[i-1][6]+dp[i-1][3]
                else:
                    dp[i][j]=dp[i-1][2]
            elif j==3:
                if R>>i&1==1:
                    dp[i][j]=dp[i-1][7]+2*dp[i-1][3]
                else:
                    dp[i][j]=dp[i-1][3]
            elif j==4:
                if L>>i&1==1:
                    dp[i][j]=dp[i-1][5]
                else:
                    dp[i][j]=dp[i-1][7]+dp[i-1][4]
            elif j==5:
                if L>>i&1==1:
                    dp[i][j]=dp[i-1][5]
                else:
                    dp[i][j]=2*dp[i-1][5]+dp[i-1][7]
            elif j==6:
                dp[i][j]=dp[i-1][6]+dp[i-1][7]
            else:
                dp[i][j]=3*dp[i-1][7]

    return dp[-1][0]

mod=10**9+7
L,R=map(int,input().split())
print(solve(L,R)%mod)

Solution (Python):
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    def bitdp(l, r):
        n = r.bit_length()
        dp = defaultdict(int)
        dp[0, 0, 0, 0] = 1
        for i, less, greater, start in itertools.product(range(n), (0, 1), (0, 1), (0, 1)):
            R_ = 1 if less else (r>>(n-i-1))&1
            L_ = 0 if greater else (l>>(n-i-1))&1
            for y in range(R_ + 1):
                for x in range(L_, y + 1):
                    less_ = less or y < R_
                    greater_ = greater or L_ < x
                    start_ = start or (y==1 and x==1)

                    if not start and (y==1 and x==0):
                        
                        continue

                    dp[i + 1, less_, greater_, start_] += dp[i, less, greater, start]
                    dp[i + 1, less_, greater_, start_] %= mod
                    

        
        

        res = sum(dp[n, less, greater, 1] for less, greater in itertools.product((0, 1), (0, 1)))
        return res
    L, R = LI()
    ans = bitdp(L,R) % mod
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
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, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
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



l, r = LI()
L = r.bit_length()
dp = [[[[0] * 2 for _ in range(2)] for _ in range(2)] for _ in range(L+1)]
dp[0][0][0][0] = 1


for i in range(L):
    rd = r >> L - i - 1 & 1
    ld = l >> L - i - 1 & 1
    for l_flg in range(2):
        for r_flg in range(2):
            for c in range(2):
                for ri, li in ((1, 0), (1, 1), (0, 0)):
                    if c == 0 and ri == 1 and li == 0:
                        continue
                    if (l_flg == 0 and li < ld) or (r_flg == 0 and ri > rd):
                        continue
                    dp[i + 1][l_flg or li > ld][r_flg or ri < rd][c or (ri == 1 and li == 1)] += dp[i][l_flg][r_flg][c]
                    dp[i + 1][l_flg or li > ld][r_flg or ri < rd][c or (ri == 1 and li == 1)] %= mod

ret = 0
for a in range(2):
    for b in range(2):
        for d in range(2):
            ret += dp[L][a][b][d]

print(ret % mod)

Solution (Python):
l,r = map(int,input().split())
lb = l.bit_length()
rb = r.bit_length()
ans = 0
mod = 10**9+7
def ignorel(r):
  ret = 0
  cntr = 0
  rb = r.bit_length()
  for i in range(rb-1)[::-1]:
    if r&1<<i:
      ret += 2**cntr*3**i
      cntr += 1
  ret += 2**cntr
  return ret%mod
def ignorer(l):
  cntl = 0
  ret = 0
  lb = l.bit_length()
  for i in range(lb)[::-1]:
    if l&1<<i == 0:
      ret += 2**cntl*3**i
      cntl += 1
  ret += 2**cntl
  return ret%mod
for i in range(lb+1,rb):
  ans += 3**(i-1)
  ans %= mod
if lb != rb:
  ans += ignorer(l)
  ans += ignorel(r)
  ans %= mod
  print(ans)
else:
  def from0(x):
    if x == 0:
      return 1
    elif x == 1:
      return 3
    xb = x.bit_length()
    ret = 3**(xb-1)+2*from0(x-(1<<(xb-1)))
    return ret
  def calc(l,r):
    ret = 0
    lb = l.bit_length()
    rb = r.bit_length()
    if l > r:
      return 0
    if l == r:
      return 1
    if l == 2**(lb-1):
      return ignorel(r)
    elif r == 2**rb-1:
      return ignorer(l)
    for i in range(lb)[::-1]:
      if l&1<<i == 0 and r&1<<i:
        ret += from0((1<<i)-1-(l&(1<<i)-1))
        ret += from0(r&((1<<i)-1))
        ret += calc((l&((1<<i)-1))+(1<<i),(r&((1<<i)-1))+(1<<i))
        break
    return ret%mod
  ans += calc(l,r)
  print(ans%mod)

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 l[pos] == '0' or flagX:
      ret += f(pos - 1, flagX, 1 if flagY or r[pos] == '1' else 0, flagZ)
    
    if (l[pos] == '0' or flagX) and (r[pos] == '1' or flagY) and flagZ:
      ret += f(pos - 1, flagX, flagY, flagZ)
    
    if r[pos] == '1' or flagY:
      ret += f(pos - 1, 1 if l[pos] == '0' or flagX else 0, 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
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):
MOD = 10**9 + 7
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * (m.i if isinstance(m, mint) else m) % MOD)
    def __sub__(self, m):
        t = self.i - m.i
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        res = 1
        while(m > 0):
            if m & 1:
                res = res * i % MOD 
            i = i * i % MOD
            m >>= 1
        return mint(res)
    def __truediv__(self, m):
        return mint(self.i * (m ** (MOD - 2)).i % MOD)
    def __repr__(self):
        return repr(self.i)

L, R = map(int, input().split())
dp = [[mint(0) for _ in range(4)] for _ in range(61)]

for d in range(60, 0, -1):
    l = L >> d - 1 & 1
    r = R >> d - 1 & 1
    
    if (L >> d - 1) == 0:
        if (R >> d - 1) > 1:
            dp[d-1][3] += 1
        elif (R >> d - 1) == 1:
            dp[d-1][2] += 1
    elif (L >> d - 1) == 1:
        if (R >> d - 1) > 1:
            dp[d-1][1] += 1
        else:
            dp[d-1][0] += 1

    
    if l == r:
        dp[d-1][0] += dp[d][0]
    elif l < r:
        dp[d-1][0] += dp[d][0]
        dp[d-1][1] += dp[d][0]
        dp[d-1][2] += dp[d][0]
    
    if l == 0:
        dp[d-1][1] += dp[d][1] * 2
        dp[d-1][3] += dp[d][1]
    else:
        dp[d-1][1] += dp[d][1]
    
    if r == 1:
        dp[d-1][2] += dp[d][2] * 2
        dp[d-1][3] += dp[d][2]
    else:
        dp[d-1][2] += dp[d][2]
    
    dp[d-1][3] += dp[d][3] * 3

print(sum(dp[0]))

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):
def main():
    import sys
    input = sys.stdin.readline

    L, R = map(int, input().split())
    N = R.bit_length()
    mod = 1000000007

    dp = [[[0] * 2 for _ in range(4)] for _ in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        l = L>>(N-i-1)&1
        r = R>>(N-i-1)&1

        
        for j in range(2):
            dp[i+1][0][j] = (dp[i+1][0][j] + dp[i][0][j] * int(l == r == 0))%mod
            dp[i+1][1][j] = (dp[i+1][1][j] + dp[i][0][j] * int(r==1 and l==0) + dp[i][1][j] * int(l==0))%mod
            dp[i+1][2][j] = (dp[i+1][2][j] + dp[i][2][j] * int(r==0))%mod
            dp[i+1][3][j] = (dp[i+1][3][j] + dp[i][2][j] * int(r==1) + dp[i][3][j])
        
        dp[i+1][0][1] = (dp[i+1][0][1] + dp[i][0][1] * int(l==0 and r==1))%mod
        dp[i+1][1][1] = (dp[i+1][1][1] + dp[i][1][1] * int(l==0))%mod
        dp[i+1][2][1] = (dp[i+1][2][1] + dp[i][2][1] * int(r==1))%mod
        dp[i+1][3][1] = (dp[i+1][3][1] + dp[i][3][1])%mod
        
        dp[i+1][0][1] = (dp[i+1][0][1] + sum(dp[i][0]) * int(l==r==1))%mod
        dp[i+1][1][1] = (dp[i+1][1][1] + sum(dp[i][1]) * int(l==1))%mod
        dp[i+1][2][1] = (dp[i+1][2][1] + sum(dp[i][0]) * int(r==1 and l==0) + sum(dp[i][2] * int(r==1)))%mod
        dp[i+1][3][1] = (dp[i+1][3][1] + sum(dp[i][1]) * int(l==0) + sum(dp[i][3]))

    ans = 0
    for j in range(4):
        ans += dp[-1][j][1]
    print(ans%mod)


if __name__ == '__main__':
    main()

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

L, R = map(int, input().split())
Rb, Lb = [0], [0]
for i in range(K):
    Rb.append((R>>i)%2)
    Lb.append((L>>i)%2)
    if Rb[-1]:
        Rm = i+1
    if Lb[-1]:
        Lm = i+1
dp =[[1, 1, 1, 1] for _ in range(K+1)]
r = 0
for i in range(1, K+1):
    dp[i][0] = dp[i-1][0] * 3 % mod
    if Rb[i]:
        dp[i][1] = dp[i-1][1] * 2 + dp[i-1][0] % mod
    else:
        dp[i][1] = dp[i-1][1]

    if Lb[i]:
        dp[i][2] = dp[i-1][2]
    else:
        dp[i][2] = dp[i-1][2] * 2 + dp[i-1][0] % mod

    if Rb[i] and Lb[i]:
        dp[i][3] = dp[i-1][3]
    elif Rb[i]:
        dp[i][3] = dp[i-1][1] + dp[i-1][2] + dp[i-1][3] % mod
    elif Lb[i]:
        dp[i][3] = 0
    else:
        dp[i][3] = dp[i-1][3]

    if Rm > i and Lm < i:
        r += dp[i-1][0]
    elif Rm > i and Lm == i:
        
        r += dp[i-1][2]
    elif Rm == i and Lm < i:
        r += dp[i-1][1]
    elif Rm == i and Lm == i:
        r += dp[i-1][3]
    else:
        r += 0
    r = r % mod
print(r)

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

dp = [[[[-1 for _ in range(2)] 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]
    res = 0
    if a or l[n]=='0':
        res += f(n-1,a,1 if r[n]=='1' else b,c)
    if (a or l[n]=='0') and (b or r[n]=='1') and c:
        res += f(n-1,a,b,c)
    if b or r[n]=='1':
        res += f(n-1,1 if l[n]=='0' else a,b,1)
    res %= mod
    dp[n][a][b][c] = res
    return res

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

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():
    L,R=map(int,input().split())
    L=map(int,bin(L)[2:].zfill(60))
    R=map(int,bin(R)[2:].zfill(60))

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

    for l,r in zip(L,R):
        ndp=[[[0]*2 for _ in range(2)] for _ in range(2)]
        for msb,mt,lt,x,y in product(range(2),repeat=5):
            if((not msb) and (x!=y)): continue
            if((not mt) and l>x): continue
            if((not lt) and y>r): continue
            if(x>y): continue
            ndp[max(msb,x*y==1)][max(mt,l<x)][max(lt,y<r)]+=dp[msb][mt][lt]
            ndp[max(msb,x*y==1)][max(mt,l<x)][max(lt,y<r)]%=MOD
        dp=ndp

    print(sum(dp[msb][mt][lt] for msb,mt,lt in product(range(2),repeat=3))%MOD)
resolve()

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():
    L,R=map(int,input().split())
    L=bin(L)[2:].zfill(60)
    R=bin(R)[2:].zfill(60)

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

    for l,r in zip(L,R):
        l=int(l); r=int(r)
        ndp=[[[0]*2 for _ in range(2)] for _ in range(2)]
        for msb,mt,lt,x,y in product(range(2),repeat=5):
            if((not msb) and (x!=y)): continue
            if((not mt) and l>x): continue
            if((not lt) and y>r): continue
            if(x>y): continue
            ndp[max(msb,x*y==1)][max(mt,l<x)][max(lt,y<r)]+=dp[msb][mt][lt]
            ndp[max(msb,x*y==1)][max(mt,l<x)][max(lt,y<r)]%=MOD
        dp=ndp

    print(sum(dp[msb][mt][lt] for msb,mt,lt in product(range(2),repeat=3))%MOD)
resolve()

Solution (Python):
def p_f():
    from itertools import product
    L, R = map(int, input().split())
    mod = 10 ** 9 + 7
    
    dp = [[[[0] * 2 for _ in range(2)] for _ in range(2)] for _ in range(61)]
    dp[60][0][0][0] = 1
    for i in reversed(range(60)):
        
        lb = L >> i & 1
        rb = R >> i & 1
        for j, k, l in product(range(2), repeat=3):
            
            pre = dp[i + 1][j][k][l]
            for x, y in product(range(2), repeat=2):
                nj, nk, nl = j, k, l
                if x and (not y):  
                    continue
                if (not l) and x != y:
                    continue
                if x and y:
                    nl = 1
                
                if (not j) and (not x) and lb:
                    continue
                if x and (not lb):
                    nj = 1
                
                if (not k) and y and (not rb):
                    continue
                if (not y) and rb:
                    nk = 1
                dp[i][nj][nk][nl] += pre

    ans = 0
    for j, k, l in product(range(2), repeat=3):
        ans += dp[0][j][k][l]
        ans %= mod
    print(ans)


if __name__ == '__main__':
    p_f()

Solution (Python):
def p_f():
    L, R = map(int, input().split())
    mod = 10 ** 9 + 7
    
    dp = [[[[0] * 2 for _ in range(2)] for _ in range(2)] for _ in range(61)]
    dp[60][0][0][0] = 1
    for i in reversed(range(60)):
        
        lb = L >> i & 1
        rb = R >> i & 1
        for j in range(2):
            for k in range(2):
                for l in range(2):
                    
                    pre = dp[i + 1][j][k][l]
                    for x in range(2):
                        for y in range(2):
                            nj, nk, nl = j, k, l
                            if x and (not y):  
                                continue
                            if (not l) and x != y:
                                continue
                            if x and y:
                                nl = 1
                            
                            if (not j) and (not x) and lb:
                                continue
                            if x and (not lb):
                                nj = 1
                            
                            if (not k) and y and (not rb):
                                continue
                            if (not y) and rb:
                                nk = 1
                            dp[i][nj][nk][nl] += pre

    ans = 0
    for j in range(2):
        for k in range(2):
            for l in range(2):
                ans += dp[0][j][k][l]
                ans %= mod
    print(ans)

if __name__ == '__main__':
    p_f()

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():
    L,R=map(int,input().split())
    L=bin(L)[2:].zfill(60)
    R=bin(R)[2:].zfill(60)
    dp=[[[0]*2 for _ in range(2)] for _ in range(2)]
    dp[0][0][0]=1 

    for l,r in zip(L,R):
        l=int(l); r=int(r)
        ndp=[[[0]*2 for _ in range(2)] for _ in range(2)]
        for x,y,mt,lt,msb in product(range(2),repeat=5):
            if((not mt) and l>x): continue
            if((not lt) and y>r): continue
            if((not msb) and x!=y): continue
            if(x>y): continue
            ndp[max(mt,l<x)][max(lt,y<r)][max(msb,x*y)]+=dp[mt][lt][msb]
            ndp[max(mt,l<x)][max(lt,y<r)][max(msb,x*y)]%=MOD
        dp=ndp

    print(sum(dp[mt][lt][msb] for mt,lt,msb in product(range(2),repeat=3))%MOD)
resolve()

Solution (Python):
l,r=map(int,input().split())
M=len(bin(r))-2
L=format(l,"b").zfill(M)
R=format(r,"b")
mod=10**9+7
dp=[[0 for l in range(70)] for i in range(5)]
if L[0]=="1":
  dp[2][0]=1
else:
  dp[3][0]=1
  dp[0][0]=1
for i in range(1,M):
  if L[i]=="1" and R[i]=="1":
    dp[1][i]=(dp[0][i-1]+dp[1][i-1])%mod
    dp[2][i]=(dp[2][i-1])%mod
    dp[3][i]=(2*dp[3][i-1])%mod
    dp[4][i]=(dp[3][i-1]+3*dp[4][i-1])%mod
  elif L[i]=="1" and R[i]=="0":
    dp[1][i]=dp[1][i-1]+dp[0][i-1]
    dp[3][i]=dp[3][i-1]
    dp[4][i]=(dp[4][i-1]*3)%mod
  elif L[i]=="0" and R[i]=="1":
    dp[0][i]=dp[0][i-1]
    dp[1][i]=(2*dp[1][i-1]+dp[2][i-1])%mod
    dp[2][i]=dp[2][i-1]
    dp[3][i]=(dp[2][i-1]+dp[3][i-1]*2)%mod
    dp[4][i]=(dp[0][i-1]+dp[1][i-1]+dp[3][i-1]+dp[4][i-1]*3)%mod
  else:
    dp[0][i]=dp[0][i-1]
    dp[1][i]=(dp[1][i-1]*2)%mod
    dp[2][i]=dp[2][i-1]
    dp[3][i]=(dp[3][i-1])%mod
    dp[4][i]=(dp[0][i-1]+dp[1][i-1]+dp[4][i-1]*3)%mod
ans=0
for i in range(5):
  ans+=dp[i][M-1]
  ans%=mod
print(ans)

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=R.bit_length()
    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()