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.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics


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


def rand(l, r):
	mod = 10 ** 9 + 7
	binary = bin(l)[2:]
	(a, b, res) = (1, 0, 0)
	for i in range(len(binary) - 1, -1, -1):
		if binary[i] == '1':
			res += a * min(a - b, r - l + 1)
			res %= mod
			b += a
		a *= 2
	return res
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(rand(a, b))


MOD = int(10 ** 9) + 7
for _ in range(int(input())):
	(L, R) = map(int, input().split())
	ans = 0
	for i in range(0, 61):
		pw = 1 << i
		if L & pw == 0:
			continue
		diff = pw - 1 - (L & pw - 1) + 1
		ans += min(diff, R - L + 1) % MOD * (pw % MOD) % MOD
		ans %= MOD
	ans %= MOD
	print(ans)


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


MVAL = 1000000007

def rangeand(low, hi):
	odf = hi - low + 1
	ra = 0
	p2 = 1
	lmd = 0
	while low & p2 == 0:
		p2 *= 2
	pmdf = p2
	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')


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


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)


modulo = int(1000000000.0) + 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
		curr *= 2
	print(ans)


e = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	ans = 0
	s = '{0:0b}'.format(a)
	s = s[-1::-1]
	for i in range(len(s)):
		if s[i] == '1':
			d = pow(2, i)
			x = a % d
			m = d - x
			n = b - a + 1
			ans = (ans + d * min(m, n)) % e
	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)


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) = map(int, input().split())
	print(rangeand(l, r))


for _ in [0] * int(input()):
	(L, R) = [int(x) for x in input().split()]
	LB = bin(L)[2:]
	product = 1
	has = 0
	res = 0
	for i in range(len(LB) - 1, -1, -1):
		if LB[i] == '1':
			res += product * min(product - has, R - L + 1)
			res %= 1000000007
			has += product
		product *= 2
	print(res)


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)


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


mod = int(1000000000.0) + 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)


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)


t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	(l, r) = map(int, input().split())
	if l == r:
		print(l % mod)
		continue
	a = bin(l)[2:]
	b = bin(r)[2:]
	a = '0' * (len(b) - len(a)) + a
	ind = 0
	while a[ind] == b[ind]:
		ind += 1
	ans = 0
	cnt = 0
	flag = 0
	for i in range(len(a) - 1, -1, -1):
		if flag == 1:
			break
		if a[i] == '0':
			cnt += 1
			if i == ind:
				flag = 1
			continue
		if i == len(a) - 1:
			ans += 1
		else:
			ans += 2 ** cnt * (2 ** cnt - 1 - int(a[i + 1:], 2) + 1)
		if i == ind:
			break
		cnt += 1
	for i in range(ind - 1, -1, -1):
		if a[i] == '0':
			cnt += 1
			continue
		if i == len(a) - 1:
			ans += 1
		else:
			ans += 2 ** cnt * (int(b[i + 1:], 2) - int(a[i + 1:], 2) + 1)
		cnt += 1
	print(ans % mod)


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


for t in range(int(input())):
	(c, c1, summ) = (0, 0, 0)
	M = 1000000007
	(l, r) = list(map(int, input().split()))
	for i in range(60):
		if l & 1 << i:
			summ += min(r - l + 1, c1 - c + 1) % M * (1 << i) % M % M
			c += 1 << i
		c1 += 1 << i
	print(summ % M)


T = int(input())
for _ in range(T):
	(a, b) = map(int, input().split())
	a1 = a
	b1 = b
	p = a
	ans = 0
	x = 1
	y = a - 1
	z = a
	while a > 0:
		r = a % 2
		if r == 1:
			z = p + x - 1
			if z <= b:
				ans = ans + p * (z - y)
			else:
				ans += p * (b - y)
				break
			y = z
			p = p - x
		a = a // 2
		x = x * 2
		ans = ans % 1000000007
	print(ans % 1000000007)


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)


MOD = 1000000007
a = int(input())
for i in range(a):
	(x, y) = 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)


from sys import stdin

def solve():
	for _ in range(int(stdin.readline())):
		(l, r) = map(int, stdin.readline().split())
		a = bin(l)[2:]
		n = len(a)
		(ci, k, res) = (0, 0, 0)
		for i in range(n):
			if a[n - 1 - i] == '1':
				k = l + (2 ** i - (2 ** i - 1 & l))
				ci = min(k - l, r - l + 1)
				res += ci * 2 ** i
		print(res % 1000000007)
solve()


for _ in range(int(input())):
	(l, r) = map(int, input().split())
	binary = bin(l)[2:]
	(a, b, s) = (1, 0, 0)
	for i in range(len(binary) - 1, -1, -1):
		if binary[i] == '1':
			s += a * min(a - b, r - l + 1)
			s %= 1000000007
			b += a
		a *= 2
	print(s)


t = int(input())
p = pow(10, 9) + 7
p = int(p)
while t:
	t -= 1
	(l, r) = map(int, input().split())
	f = bin(l)[2:]
	po = 1
	s = 0
	res = 0
	for i in range(len(f) - 1, -1, -1):
		if f[i] == '1':
			res += po * min(po - s, r - l + 1)
			res = res % p
			s += po
		po = po * 2
	print(res)


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)


import math
t = int(input())
mod = 10 ** 9 + 7
for j in range(t):
	(l, r) = map(int, input().split())
	count1 = 0
	count2 = 0
	result = 0
	for i in range(60):
		count2 += 1 << i
		if l & 1 << i:
			count1 += 1 << i
			mini = min(r - l + 1, count2 - count1 + 1)
			result += mini % mod * ((1 << i) % mod) % mod
	print(result % mod)


import math
for _ in range(int(input())):
	(l, r) = list(map(int, input().split()))
	p = pow(2, 80)
	(ltmp, rtmp) = (l, r)
	b1 = int(math.log2(l)) + 1
	b2 = int(math.log2(r)) + 1
	ans = 0
	while l > 0:
		while p > l:
			p //= 2
		rem = p * 2 - l
		ans += rem * p
		l %= p
	if b1 != b2:
		print(ans % (10 ** 9 + 7))
	else:
		p = pow(2, 80)
		while r:
			while p > r:
				p //= 2
			br = int(math.log2(r))
			if ltmp & pow(2, br) == 0:
				rem = p * 2 - r
				rem -= 1
				r %= p
				break
			else:
				rem = p * 2 - r
				rem -= 1
				ans -= rem * p
				r %= p
		print(ans % (10 ** 9 + 7))


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


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	a1 = bin(l)[2:]
	if l == 1:
		print(1)
	else:
		k = []
		k1 = []
		su = 0
		if a1[-1] == '1':
			k.append(1)
			k1.append(1)
			su = 1
		p = len(a1)
		ca = 2
		for i in range(p - 2, -1, -1):
			if a1[i] == '1':
				k.append(ca)
				k1.append(ca - su)
				su += ca
			ca *= 2
		re = r - l + 1
		ans = 0
		for i in range(len(k)):
			ans += k[i] % mod * min(re, k1[i]) % mod % mod
			ans %= mod
		print(ans)


mod = 10 ** 9 + 7
for i in range(int(input())):
	(l, r) = [int(i) for i in input().split()]
	if l == r:
		print(l % mod)
		continue
	res = 0
	diff = r - l + 1
	i = 1
	j = 1
	temp = l
	while temp:
		if temp & 1:
			temp2 = l & i
			k = min(r + 1 - l, i + 1 - temp2)
			res = (res + j * k) % mod
		temp = temp // 2
		i = i * 2 + 1
		j = j * 2
	print(res % mod)


MOD = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	(l, r) = map(int, input().split())
	bl = bin(l)[2:]
	sum = 0
	val = 1
	s = 0
	for i in range(len(bl) - 1, -1, -1):
		if bl[i] == '1':
			sum += val * min(val - s, r - l + 1)
			sum = sum % MOD
			s += val
		val *= 2
	print(sum)


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)


t = int(input())
mod = 10 ** 9 + 7
for i in range(t):
	(a, b) = (int(x) for x in input().split())
	sum = a
	check = 2
	while check <= a:
		rem = a // check
		to = (rem + 1) * check - a - 1
		if to > b - a:
			to = b - a
		if rem % 2 != 0:
			sum = sum + to * (check % mod)
			sum = sum % mod
		check = check * 2
	print(sum % mod)


mod = 1000000007
t = int(input())
while t:
	(l, r) = 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


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)


for _ in range(int(input())):
	(l, r) = map(int, input().split())
	a = 1
	b = 0
	s = 0
	x = l
	binary = ''
	while l > 0:
		binary += str(l % 2)
		l //= 2
	for i in binary:
		if i == '1':
			s += a * min(a - b, r - x + 1) % 1000000007
			s %= 1000000007
			b += a
		a *= 2
	print(s)


import math
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	ans = 0
	for i in range(60):
		if l & 1 << i > 0:
			pr = min((1 << i) - (l & (1 << i) - 1), r - l + 1)
			ans += pr * (1 << i)
	print(ans % (10 ** 9 + 7))


M = int(1000000000.0 + 7)
T = int(input())
for i in range(T):
	(L, R) = map(int, input().split())
	ans = 0
	if L == R:
		ans = L % M
	else:
		b1 = bin(L)[2:]
		b2 = bin(R)[2:]
		val = -1
		if len(b2) == len(b1):
			for j in range(len(b1)):
				if b1[j] != b2[j]:
					val = j
					break
		cur = L
		zl = len(b1) - 1
		last = 0
		ans = L % M
		cv = 1
		while zl > val:
			if b1[zl] == '0':
				ans = (ans + cur % M * cv % M) % M
			else:
				cur -= cv
			cv <<= 1
			zl -= 1
		if val != -1:
			pp = b2[val + 1:]
			cv = int(pp, 2) + 1
			ans = (ans + cur % M * cv % M) % M
	print(ans % M)


for i in range(int(input())):
	(l, r) = map(int, input().split())
	binl = bin(l)[2:]
	diff = r - l + 1
	(ans, ans1, ans2) = (0, 0, 0)
	for j in range(len(binl)):
		if diff <= 0:
			break
		if binl[len(binl) - j - 1] == '1':
			x = 2 ** j
			ans += (l - ans2) % (10 ** 9 + 7) * min(diff, x - ans1) % (10 ** 9 + 7) % (10 ** 9 + 7)
			ans %= 10 ** 9 + 7
			diff -= x - ans1
			ans1 = 2 * x
			ans2 += x
	print(ans)


from math import log2
rightmost = lambda n: int(log2(n & -n))
bini = lambda x: bin(x)[2:]
mod = int(1000000000.0 + 7)

def solve(l, r):
	res = l
	ans = 0
	for i in range(l, r + 1):
		res = res & i
		ans += res
	return ans

def optimized(l, r):
	if l == r:
		return l
	ans = 0
	val = l
	cnt = 1 << rightmost(l)
	ans = 0
	arr = [l, val + cnt]
	while arr[-1] <= r:
		ans = ans + (arr[-1] - arr[-2]) % mod * (val % mod)
		ans = ans % mod
		val = val & val + cnt
		if val == 0:
			break
		cnt = 1 << rightmost(val)
		arr.append(cnt + val)
	ans = ans + (r - arr[-2] + 1) % mod * (val % mod)
	return ans % mod
for t in range(int(input())):
	(l, r) = map(int, input().split())
	print(optimized(l, r))


MOD = 10 ** 9 + 7
II = lambda : [int(x) for x in input().split()]
I2 = lambda : int(input())
T = int(input())
for _ in range(T):
	(L, R) = (int(x) for x in input().split())
	sum = 0
	max_R1 = 1
	while max_R1 <= L:
		max_R1 *= 2
	val = int(max_R1 / 2)
	max_R1 -= 1
	while val >= 1:
		if L & val:
			R = min(R, max_R1)
			a = R - L + 1
			count = min(val, a) % MOD
			sum += val * count % MOD
			L = L - val
			R -= val
		max_R1 -= val
		val = int(val / 2)
	print(sum % MOD)


for _ in range(int(input())):
	(l, r) = map(int, input().split())
	mod = 10 ** 9 + 7
	binary = bin(l)[2:]
	(a, b, s) = (1, 0, 0)
	for i in range(len(binary) - 1, -1, -1):
		if binary[i] == '1':
			s += a * min(a - b, r - l + 1)
			s %= mod
			b += a
		a *= 2
	print(s)


t = int(input())
for _ in range(t):
	(l, r) = [int(v) for v in input().split()]
	b = bin(l)[2:]
	p = 1
	s = 0
	res = 0
	for i in range(len(b) - 1, -1, -1):
		if b[i] == '1':
			res += p * min(p - s, r - l + 1)
			res %= 1000000007
			s += p
		p *= 2
	print(res)