You are given positive integers $L$ and $R$. You have to find the sum
S=∑i=LR(L∧(L+1)∧…∧i),S=∑i=LR(L∧(L+1)∧…∧i),S = \sum_{i=L}^R \left(L \wedge (L+1) \wedge \ldots \wedge i\right) \,,
where $\wedge$ denotes the bitwise AND operation. Since the sum could be large, compute it modulo $10^9+7$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $L$ and $R$.

-----Output-----
For each test case, print a single line containing one integer — the sum $S$ modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le L \le R \le 10^{18}$

-----Example Input-----
2
1 4
4 10

-----Example Output-----
1
16

-----Explanation-----
Example case 1: The sum is 1 + 1 AND 2 + 1 AND 2 AND 3 + 1 AND 2 AND 3 AND 4 = 1 + 0 + 0 + 0 = 1.
Example case 2: The sum is 4 + 4 AND 5 + 4 AND 5 AND 6 + 4 AND 5 AND 6 AND 7 + … + 4 AND 5 AND … AND 10 = 4 + 4 + … + 0 = 16.

Difficulty: interview

Starter code:

Solutions:
l= []
for i in range(62):
 l.append(2**i)
T = int(input())

flag = 0
for t in range(T):
 L,R = [int(i) for i in input().split()]
 bL = bin(L)
 lL = len(bL)-2
 index = 1
 ans = 0
 temp = 0
 
 while(index<=lL):
  temp = L%l[index]
  if temp>=l[index-1]:
   if(l[index]-temp<=R-L+1):
    ans= (ans +(l[index-1])*(l[index]-temp))%1000000007
   else :
    ans=(ans+(l[index-1])*(R-L+1))%1000000007
   
   
  index+=1
 print(ans)
#    4378578345 584758454958
# 18091037982636824985 8589934592 4429185025 4294967296


mod=int(1e9)+7
t=int(input())
while t:
 t-=1
 l, r= map(int , input().split())
 binl=bin(l)[:1:-1]
 f, cnt, ans=1, 0, 0
 for i in binl:
  if i=='1':
   ans= (ans+f*min(f-cnt, r-l+1))%mod
   cnt+=f
  f*=2
 print(ans)

MOD = 1000000007
a=int(input())
for i in range(a):
 
 x,y = list(map(int,input().split()))
 start = x
 end = y
 ans = x
 prev = x
 z = x
 j=-1
 while(start!=0):
  j+=1
   
  if((z&1) != 0):
    
   add = 1 << j
   next = (start + add)
   if(next > end):
    ans=(ans+(((end-prev))*(start)))
    
    break
   
   ans =(ans+ ((((next-prev-1))*(start)) + (start-add)))
   
   ans%=MOD
   start-=add
   if(next == end):
    break
   
   prev = next
   
  
  
  z = z>>1
 
 print(ans%MOD)
 





MOD = 1000000007
a=int(input())
for i in range(a):
 
 x,y = list(map(int,input().split()))
 start = x
 end = y
 ans = x
 prev = x
 z = x
 j=-1
 while(start!=0):
  j+=1
   
  if((z&1) != 0):
    
   add = pow(2,j)
   next = (start + add)
   if(next > end):
    ans=(ans+(((end-prev))*(start)))
    
    break
   
   ans =(ans+ ((((next-prev-1))*(start)) + (start-add)))
   
   ans%=MOD
   start-=add
   if(next == end):
    break
   
   prev = next
   
  
  
  z = z>>1
 
 print(ans%MOD)
 





t=int(input())
while(t):
 t-=1
 l,r = [int(i) for i in input().split()]
 bl = bin(l)[2:]
 bl = bl[::-1]
 sub = 0
 val = 1
 ans = 0
 mod = 10**9 + 7
 for i in range (len(bl)):
  if bl[i] == '1':
   ans+= val*(min(val-sub,r-l+1))%mod
   sub+=val
  val*=2
 print(ans%mod)


m = [1]
mod = 10**9+7
for i in range (60):
 a = m[-1]
 a *=2
 a %=mod
 m.append(a)
 
for i in range (int(input())):
 L,R = map(int,input().split())
 tmp = 0
 l = bin(L)[2:]
 r = bin(R)[2:]
 a = 1
 ans = L%mod
 for i in range (1,len(l)+1):
  if(l[-i]=='0'):
   if tmp+2**(i-1)<=R-L:
    ans +=((m[i-1])*(L-a+1))%mod
    tmp +=2**(i-1)
    ans %=mod
   else:
    ans +=((R-L-tmp)*(L-a+1))%mod
    ans %=mod
    break
  else:
   a +=m[i-1]
 print(ans)

mod = 10**9+7
t = int(input())
while(t>0):
 l, r = map(int, input().split())
 ans = 0
 for i in range(63):
  if(l&(1<<i)):
   x =(1<<i) - (l&((1<<i)-1))
   x = min(x, (r-l+1))
   ans += x*(1<<i)
 print(ans%mod)
 
 
 
 t = t-1

from sys import stdin, stdout
mod=(1000*1000*1000+7)
for i in range(int(stdin.readline())):
 l,r=map(int,stdin.readline().split())
 act=0
 req=0
 ans=0
 for i in range(60):
  val=min(r-l+1,req-act+1)
  val%=mod
  if(l&(1<<i)):
   ans+=(val*((1<<i)%mod))%mod
   ans%=mod
   act+=(1<<i)
  req+=(1<<i)
 print(ans)

from sys import stdin
mod=(1000*1000*1000+7)
for i in range(int(stdin.readline())):
 l,r=map(int,stdin.readline().split())
 act=0
 req=0
 ans=0
 for i in range(60):
  val=min(r-l+1,req-act+1)
  val%=mod
  if(l&(1<<i)):
   ans+=(val*((1<<i)%mod))%mod
   ans%=mod
   act+=(1<<i)
  req+=(1<<i)
 print(ans)

# Ankan Kumar Das
# Date : 27/02/2020
MOD = 10**9 + 7
for _ in range(int(input())):
 l, r = map(int, input().split())
 max_no_elm = r - l + 1
 ans, multi, l_p, r_p = 0, 1, l, 0
 while l_p != 0:
  curr_bit = l_p & 1
  if curr_bit == 1:
   no_elm = multi - r_p
   ans = (ans + multi * min(no_elm, max_no_elm)) % MOD
  l_p, r_p = l_p >> 1, r_p + multi * curr_bit
  multi = multi << 1
 print(ans)

# https://www.codechef.com/problems/RGAND

MVAL = 1000000007

def rangeand(low,hi):
 odf = hi - low + 1
 ra = 0
 p2 = 1
 lmd = 0
 while (low&p2) == 0:
  p2 *= 2
 pmdf = p2 # lowest set bit splits an interval
 if pmdf >= odf:
  return (odf*low)%MVAL
 while p2<=low:
  if (low & p2):
   lmd += p2
   ra += (pmdf*p2)%MVAL
  else:
   pmdf += p2
   if pmdf >= odf:
    ra += (odf*(low-lmd))%MVAL
    break
  p2 *= 2

 return ra%MVAL

t = int(input())
ans =[]
for ti in range(t):
 l,r = map(int,input().split())

 ans.append( rangeand(l,r) )

print( *ans, sep='\n' )


# https://www.codechef.com/problems/RGAND

MVAL = 1000000007

def rangeand(low,hi):
 ra = 0
 p2 = 1
 lmd = 0
 ldv =low
 hdv = hi
 while p2<=low:
  thisbit = low & p2
  p2 *= 2
  ldv //= 2
  hdv //= 2
  if ldv == hdv:
   ra += ((hi+1-low)*(low-lmd))%MVAL
   break
  elif thisbit > 0:
   lmd += thisbit
   ra += ((p2-lmd)*thisbit)%MVAL
 return ra%MVAL

t = int(input())
for ti in range(t):
 l,r = list(map(int,input().split()))

 print( rangeand(l,r) )


# https://www.codechef.com/problems/RGAND

MVAL = 1000000007

def rangeand(low,hi):
 ra = 0
 p2 = 1
 while p2<=low:
  ld,lm = divmod(low,p2*2)
  hd,hm = divmod(hi,p2*2)
  if ld == hd:
   ra += ((hm-lm+1)*(p2 & lm))%MVAL
  else:
   ra += ((p2*2-lm)*(p2 & lm))%MVAL
  p2 *= 2
 return ra%MVAL

t = int(input())
for ti in range(t):
 l,r = list(map(int,input().split()))

 print( rangeand(l,r) )


for _ in range(int(input())):
 a,b=map(int,input().split())
 st=bin(a)[2:]
 s=0;m=1;ans=0
 for i in range(len(st)-1,-1,-1):
  if(st[i]=="1"):
   ans += m*min(m-s,b-a+1)
   ans %= 1000000007
   s+=m
  m*=2
 print(ans)

# cook your dish here

mod = 1000000007
t=int(input())
while t:
 l,r=list(map(int,input().split( )))
 ans=0
 if l==r:
  print(l%mod)
 else:
  temp = l
  i=1
  j=1
  while temp:
   if temp&1:
    tp2 = l&i
    k=min(r-l+1,i-tp2+1)
    ans=(ans+j*k)%mod
   i<<=1
   i+=1
   j<<=1
   temp>>=1
  print(ans%mod)
 t-=1


mod = 10**9 + 7
for _ in range(int(input())):
 l, r = map(int, input().split())
 z = 2
 while(z <= l):
  z *= 2
 if(r > z):
  r = z - 1
 z = z // 2
 ans = l
 lb = bin(l).replace("0b", "")
 for i in lb:
  if(i != '0'):
   h = l % z
   h = z - h - 1
   if(h >= r - l):
    g = r % z
    g = z - g - 1
    if(g < h):
     h = h - g
   ans += h * z
  z = z // 2
 print(ans % mod)

mod = 10**9 + 7
t=int(input())
for _ in range(t):
 l, r = map(int, input().split())
 z = 2
 while(z <= l):
  z *= 2
 if(r > z):
  r = z - 1
 z = z // 2
 ans = l
 lb = bin(l).replace("0b", "")
 for i in lb:
  if(i != '0'):
   h = l % z
   h = z - h - 1
   if(h >= r - l):
    g = r % z
    g = z - g - 1
    if(g < h):
     h = h - g
   ans += h * z
  z = z // 2
 print(ans % mod)

import math
for _ in range(int(input())):
 a, b = [int(i) for i in input().split()]
 ans = 1
 sum = 0
 c = int(math.log2(a))
 for i in range(c+1):
  doo = 2 ** i
  po = doo & a
  if po == doo:
   sum += min(b-a+1, ans) * doo
  else:
   ans += doo
 print(sum%1000000007)


# cook your dish here
import math
def optimalSol(a,b):
 power=int(math.log(a,2))
 add=0
 mod=10**9+7
 previous_i=-1
 present=0
 end=0
 for i in range(power+1):
  bit_add=2**i
  end+=2**i
  if a&bit_add==bit_add:
   present+=bit_add
   total_added=min(b-a+1,end-present+1)
   add+=bit_add*total_added
 return add%mod 
for _ in range(int(input())):
 a,b=list(map(int,input().split()))
 print(optimalSol(a,b))

modulo = int(1e9) + 7
for t in range(int(input())):
 l,r = map(int,input().split())
 curr = 1
 ans = 0
 for i in range(61):
  q = (l)//curr
  if q&1:
   end = min(r,(q+1)*curr-1)
   ans = (ans + (curr*(end-l+1)%modulo)%modulo)%modulo
   #print(i,end,q,curr,ans)
  curr *= 2
 print(ans)

# cook your dish here
t=int(input())
while t>0:
 a,b=list(map(int,input().split()))
 k=1
 m=a
 n=b
 sum=0
 x=0
 y=1
 while a>0:
  a=a//2
  l=m//k
  if l%2!=0:
   p=k*l
   q=k*(l+1)
  else:
   p=k*(l+1)
   q=k*(l+2)
  k*=2
  if m>=p and m<q:
   if b<q:
    o=b-m+1
    lum=((o%1000000007)*(y%1000000007))%1000000007
    sum=sum+lum
    sum=sum%1000000007
   else:
    o=q-m
    lum=((o%1000000007)*(y%1000000007))%1000000007
    sum=sum+lum
    sum=sum%1000000007
  y*=2
 print(sum)
 t-=1

t=int(input())
m=10**9+7
while t:
 p=0
 res=0
 l,r=map(int,input().split())
 d=r-l+1
 br=bin(r)[2:]
 lbr=len(br)
 l=bin(l)[2:]
 k=-1
 lol=0
 ll=len(l)
 ind=ll-1
 
 if(2**ll>r):
  for i in range(ll):
   if(l[i]=='0' and br[i]=='1'):
    ind=i
    break
  #print(ind)
  for i in range(len(l)-1,ind,-1):
   k+=1
   if(l[i]=='1'):
    a=2**k
    p+=a
    res+=(min(r+1,2**(k+1))-p)*a
  for i in range(ind+1):
   if(l[i]=='1'):
    res+=2**(ll-i-1)*d
  

 else:
  for i in range(len(l)-1,-1,-1):
   k+=1
   if(l[i]=='1'):
    a=2**k
    p+=a
    res+=(min(r+1,2**(k+1))-p)*a
 print(res%m)
 t-=1