AtCoder Beginner Contest 138 - Coincidence

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

-----Sample Output-----
3

Three pairs satisfy the condition: (2, 2), (2, 3), and (3, 3).

Difficulty: MEDIUM_HARD

Starter code:

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


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


import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
(l, r) = [int(i) for i in readline().split()]

def make_dp(init, size):
	res = '[{}]*{}'.format(init, size[-1])
	for i in reversed(size[:-1]):
		res = '[{} for _ in [0]*{}]'.format(res, i)
	return eval(res)
MOD = 10 ** 9 + 7
R = bin(r)[2:]
L = bin(l)[2:]
L = '0' * (len(R) - len(L)) + L
dp = make_dp(0, (len(R) + 1, 2, 2, 2))
dp[0][0][0][0] = 1
for (i, (r, l)) in enumerate(zip(R, L)):
	ri = int(r)
	li = int(l)
	for is_less in range(2):
		for is_more in range(2):
			for is_nonzero in range(2):
				for dl in range(0 if is_more else li, 2):
					for dr in range(dl, 2 if is_less else ri + 1):
						dp[i + 1][is_nonzero or dr != 0][is_more or li < dl][is_less or dr < ri] += dp[i][is_nonzero][is_more][is_less] * (dr == dl or is_nonzero)
						dp[i + 1][is_nonzero or dr != 0][is_more or li < dl][is_less or dr < ri] %= MOD
ans = 0
for i in range(2):
	for j in range(2):
		for k in range(2):
			ans += dp[-1][i][j][k]
print(ans % MOD)


(L, R) = map(int, input().split())
dp = []
for i in range(62):
	nowA = []
	for i in range(2):
		nowB = []
		for i in range(2):
			nowC = []
			for i in range(2):
				nowC.append(0)
			nowB.append(nowC)
		nowA.append(nowB)
	dp.append(nowA)
dp[0][0][0][0] = 1
for i in range(61):
	i += 1
	keta = 62 - i
	lb = (L >> keta - 1) % 2
	rb = (R >> keta - 1) % 2
	for j in range(2):
		for k in range(2):
			for m in range(2):
				pre = dp[i - 1][j][k][m]
				for x in range(2):
					for y in range(2):
						nj = j
						nk = k
						nm = m
						if x == 1 and y == 0:
							continue
						if x != y and m == 0:
							continue
						if j == 0 and lb == 1 and (x == 0):
							continue
						if k == 0 and rb == 0 and (y == 1):
							continue
						if j == 0 and lb == 0 and (x == 1):
							nj = 1
						if k == 0 and rb == 1 and (y == 0):
							nk = 1
						if m == 0 and x == 1 and (y == 1):
							nm = 1
						dp[i][nj][nk][nm] += dp[i - 1][j][k][m]
						dp[i][nj][nk][nm] %= 10 ** 9 + 7
ans = 0
for j in range(2):
	for k in range(2):
		ans += dp[-1][j][k][1]
print(ans % (10 ** 9 + 7))


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)


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)


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


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


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


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


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


from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)
P = 10 ** 9 + 7

@lru_cache(maxsize=None)
def subcalc(l, r):
	if l < 0 or r < 0:
		print('ERROR')
		print(('l, r =', l, r))
		print(1 // 0)
	if l > r:
		return 0
	if r == 0:
		return 1
	(aa, bb) = (l.bit_length(), r.bit_length())
	if aa == bb:
		return subcalc(l - (1 << aa - 1), r - (1 << bb - 1))
	if r & r + 1 == 0 and l == 0:
		return pow(3, r.bit_length(), P)
	t = (subcalc(l, r - (1 << bb - 1)) + subcalc(l, (1 << bb - 1) - 1) + subcalc(0, r - (1 << bb - 1))) % P
	return t

@lru_cache(maxsize=None)
def calc(L, R):
	if L < 0 or R < 0:
		print('ERROR')
		print(('l, r =', l, r))
		print(1 // 0)
	if L > R:
		return 0
	a = L.bit_length()
	b = R.bit_length()
	if b > a:
		t = (calc(L, (1 << b - 1) - 1) + calc(1 << b - 1, R)) % P
		return t
	a = 1 << L.bit_length() - 1 if L else 0
	t = subcalc(L - a, R - a)
	return t
(L, R) = list(map(int, input().split()))
print(calc(L, R))


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


from itertools import product
MOD = 10 ** 9 + 7
(L, R) = list(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(list(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])


(L, R) = list(map(int, input().split()))
ans = 0
for d in range(70):
	if d < len(bin(L)) - 3:
		LD = []
	elif d == len(bin(L)) - 3:
		LD = [i for i in range(-1, d) if i == -1 or L >> i & 1 == 0]
	else:
		LD = [d]
	if d < len(bin(R)) - 3:
		RD = [d]
	elif d == len(bin(R)) - 3:
		RD = [i for i in range(-1, d) if i == -1 or R >> i & 1 == 1]
	else:
		RD = []
	for ld in LD:
		for rd in RD:
			a = 1
			for i in range(d):
				if i < ld:
					xc = [0, 1]
				elif i == ld:
					xc = [1]
				else:
					xc = [L >> i & 1]
				if i < rd:
					yc = [0, 1]
				elif i == rd:
					yc = [0]
				else:
					yc = [R >> i & 1]
				c = 0
				for x in xc:
					for y in yc:
						if y >= x:
							c += 1
				a *= c
			ans += a
print(ans % (10 ** 9 + 7))


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)


MOD = 10 ** 9 + 7
(L, R) = [int(item) for item in input().split()]
L_blen = L.bit_length()
R_blen = R.bit_length()
dp = [[[0] * (R_blen + 1) for _ in range(2)] for _ in range(2)]
for i in range(R_blen + 1):
	L_bit = L & 1 << R_blen - i
	R_bit = R & 1 << R_blen - i
	curbit_idx = R_blen - i + 1
	if curbit_idx <= R_blen and curbit_idx >= L_blen:
		dp[R_blen == curbit_idx][L_blen == curbit_idx][i] += 1
	if not R_bit and (not L_bit):
		dp[0][0][i] += dp[0][0][i - 1]
		dp[0][0][i] += dp[0][1][i - 1]
		dp[1][1][i] += dp[1][1][i - 1]
		dp[1][0][i] += dp[1][0][i - 1]
		dp[0][0][i] += dp[0][0][i - 1]
		dp[0][1][i] += dp[0][1][i - 1]
		dp[0][1][i] += dp[0][1][i - 1]
		dp[0][0][i] += dp[0][0][i - 1]
	if R_bit and (not L_bit):
		dp[0][0][i] += dp[0][0][i - 1]
		dp[1][0][i] += dp[1][0][i - 1]
		dp[0][0][i] += dp[0][1][i - 1]
		dp[1][0][i] += dp[1][1][i - 1]
		dp[0][0][i] += dp[0][0][i - 1]
		dp[0][0][i] += dp[1][0][i - 1]
		dp[0][1][i] += dp[0][1][i - 1]
		dp[0][1][i] += dp[1][1][i - 1]
		dp[0][0][i] += dp[0][0][i - 1]
		dp[1][0][i] += dp[1][0][i - 1]
		dp[0][1][i] += dp[0][1][i - 1]
		dp[1][1][i] += dp[1][1][i - 1]
	if not R_bit and L_bit:
		dp[0][0][i] += dp[0][0][i - 1]
		dp[0][1][i] += dp[0][1][i - 1]
		dp[0][0][i] += dp[0][0][i - 1]
		dp[1][0][i] += dp[1][0][i - 1]
		dp[0][0][i] += dp[0][0][i - 1]
	if R_bit and L_bit:
		dp[0][0][i] += dp[0][0][i - 1]
		dp[1][0][i] += dp[1][0][i - 1]
		dp[0][1][i] += dp[0][1][i - 1]
		dp[1][1][i] += dp[1][1][i - 1]
		dp[0][0][i] += dp[1][0][i - 1]
		dp[0][0][i] += dp[0][0][i - 1]
		dp[1][0][i] += dp[1][0][i - 1]
		dp[0][0][i] += dp[0][0][i - 1]
	for i in range(2):
		for j in range(2):
			dp[i][j][i] %= MOD
ans = 0
for i in range(2):
	for j in range(2):
		ans += dp[i][j][-1]
		ans %= MOD
print(ans)


from functools import lru_cache
P = 10 ** 9 + 7

@lru_cache(maxsize=None)
def subcalc(l, r):
	if l > r:
		return 0
	if r == 0:
		return 1
	(aa, bb) = (l.bit_length(), r.bit_length())
	if aa == bb:
		return subcalc(l - (1 << aa - 1), r - (1 << bb - 1))
	if r & r + 1 == 0 and l == 0:
		return pow(3, r.bit_length(), P)
	return (subcalc(l, r - (1 << bb - 1)) + subcalc(l, (1 << bb - 1) - 1) + subcalc(0, r - (1 << bb - 1))) % P

@lru_cache(maxsize=None)
def calc(L, R):
	if L > R:
		return 0
	a = L.bit_length()
	b = R.bit_length()
	if b > a:
		return (calc(L, (1 << b - 1) - 1) + calc(1 << b - 1, R)) % P
	a = 1 << L.bit_length() - 1 if L else 0
	return subcalc(L - a, R - a)
(L, R) = map(int, input().split())
print(calc(L, R))


(L, R) = list(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)


(L, R) = map(int, input().split())
MOD = 10 ** 9 + 7
(*BL,) = map(int, bin(L)[2:])
(*BR,) = map(int, bin(R)[2:])
a = len(BL)
b = len(BR)
BL = [0] * (len(BR) - len(BL)) + BL
BL.reverse()
BR.reverse()
memo = [[[-1] * 2 for i in range(2)] for j in range(70)]

def dfs(i, p, q):
	if memo[i][p][q] != -1:
		return memo[i][p][q]
	if i == -1:
		memo[i][p][q] = 1
		return 1
	r = 0
	if p == q == 0:
		if BL[i] == 1 and BR[i] == 0:
			memo[i][0][0] = 0
			return 0
		if BL[i] == 1 or BR[i] == 0:
			r = dfs(i - 1, 0, 0)
		else:
			r = (dfs(i - 1, 0, 1) + dfs(i - 1, 1, 0) + dfs(i - 1, 0, 0)) % MOD
	elif p == 0:
		if BL[i] == 1:
			r = dfs(i - 1, 0, 1)
		else:
			r = (2 * dfs(i - 1, 0, 1) + dfs(i - 1, 1, 1)) % MOD
	elif q == 0:
		if BR[i] == 0:
			r = dfs(i - 1, 1, 0)
		else:
			r = (2 * dfs(i - 1, 1, 0) + dfs(i - 1, 1, 1)) % MOD
	else:
		r = 3 * dfs(i - 1, 1, 1)
	memo[i][p][q] = r
	return r
ans = 0
for l in range(a - 1, b):
	ans += dfs(l - 1, +(not a - 1 == l), +(not b - 1 == l))
print(ans % MOD)


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


from itertools import product
(L, R) = list(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)


MOD = 10 ** 9 + 7
(l, r) = map(int, input().split())

def func(x, y):
	if y == 0:
		return 1
	dp = [[0 for _ in range(6)] for _ in range(61)]
	dp[60][0] = 1
	for i in range(59, -1, -1):
		if y >> i & 1 == 0 and x >> i & 1 == 0:
			dp[i][0] = dp[i + 1][0]
			dp[i][1] = dp[i + 1][1]
			dp[i][2] = dp[i + 1][2]
			dp[i][3] = dp[i + 1][3] * 2 % MOD
			dp[i][4] = dp[i + 1][4]
			dp[i][5] = (dp[i + 1][1] + dp[i + 1][3] + dp[i + 1][5] * 3) % MOD
		elif y >> i & 1 == 1 and x >> i & 1 == 1:
			dp[i][0] = 0
			dp[i][1] = 0
			dp[i][2] = (dp[i + 1][0] + dp[i + 1][2]) % MOD
			dp[i][3] = (dp[i + 1][1] + dp[i + 1][3]) % MOD
			dp[i][4] = dp[i + 1][4] * 2 % MOD
			dp[i][5] = (dp[i + 1][4] + dp[i + 1][5] * 3) % MOD
		elif y >> i & 1 == 1 and x >> i & 1 == 0:
			dp[i][0] = 0
			dp[i][1] = (dp[i + 1][0] + dp[i + 1][1]) % MOD
			dp[i][2] = dp[i + 1][2]
			dp[i][3] = (dp[i + 1][2] + dp[i + 1][3] * 2) % MOD
			dp[i][4] = (dp[i + 1][0] + dp[i + 1][2] + dp[i + 1][4] * 2) % MOD
			dp[i][5] = (dp[i + 1][1] + dp[i + 1][3] + dp[i + 1][4] + dp[i + 1][5] * 3) % MOD
		elif y >> i & 1 == 0 and x >> i & 1 == 1:
			dp[i][0] = 0
			dp[i][1] = 0
			dp[i][2] = 0
			dp[i][3] = (dp[i + 1][1] + dp[i + 1][3]) % MOD
			dp[i][4] = dp[i + 1][4]
			dp[i][5] = dp[i + 1][5] * 3 % MOD
	return sum(dp[0]) % MOD
print(func(l, r))


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


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


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


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from functools import lru_cache
MOD = 10 ** 9 + 7

@lru_cache()
def F_naive(L, R):
	ret = 0
	ret += F((L + 1) // 2, (R + 1) // 2)
	answer = 0
	for x in range(L, R + 1):
		for y in range(x, R + 1):
			if x.bit_length() == y.bit_length() and (x ^ y) + x == y:
				answer += 1
	return answer

@lru_cache()
def F(L, R):
	if L < 0:
		L = 0
	if R < L:
		return 0
	if R == 0:
		return 0
	ret = 0
	ret += F((L + 1) // 2, R // 2)
	ret += F((L + 1) // 2, (R - 1) // 2)
	ret += G(L // 2, (R - 1) // 2)
	return ret

@lru_cache()
def G(L, R):
	if L < 0:
		L = 0
	if R < L:
		return 0
	if R == 0:
		return 1
	ret = 0
	ret += G((L + 1) // 2, R // 2)
	ret += F((L + 1) // 2, (R - 1) // 2)
	ret += G(L // 2, (R - 1) // 2)
	return ret
(L, R) = map(int, input().split())
answer = F(L, R) % MOD
print(answer)


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)


import sys
sys.setrecursionlimit(10 ** 9)
from functools import lru_cache
mod = 1000000007

@lru_cache()
def calc(l, r):
	if l > r:
		return 0
	if r == 0:
		return 1
	(b_l, b_r) = (l.bit_length(), r.bit_length())
	if b_l == b_r:
		return calc(l - (1 << b_l - 1), r - (1 << b_r - 1))
	if r == (1 << b_r - 1) - 1 and l == 0:
		return pow(3, b_r, mod)
	return (calc(l, r - (1 << b_r - 1)) + calc(l, (1 << b_r - 1) - 1) + calc(0, r - (1 << b_r - 1))) % mod

@lru_cache()
def solve(l, r):
	if l > r:
		return 0
	(b_l, b_r) = (l.bit_length(), r.bit_length())
	if b_r > b_l:
		return (solve(l, (1 << b_r - 1) - 1) + calc(0, r - (1 << b_r - 1))) % mod
	a = 1 << b_l - 1 if l else 0
	return calc(l - a, r - a)
(l, r) = map(int, input().split())
print(solve(l, r))


m = 10 ** 9 + 7
(l, r) = list(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(list(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)


(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)
		elif numl[pos] == 1:
			res = rec(pos - 1, brr, brl)
		else:
			res += 2 * rec(pos - 1, brr, 0)
			res += rec(pos - 1, brr, 1)
	elif numr[pos] == 1:
		if brl:
			res += 2 * rec(pos - 1, 0, brl)
			res += rec(pos - 1, 1, brl)
		elif 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)
	elif 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))


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


(L, R) = list(map(int, input().split()))
ans = 0
for d in range(70):
	if d < len(bin(L)) - 3:
		LD = []
	elif d == len(bin(L)) - 3:
		LD = [i for i in range(-1, d) if i == -1 or L >> i & 1 == 0]
	else:
		LD = [d]
	if d < len(bin(R)) - 3:
		RD = [d]
	elif d == len(bin(R)) - 3:
		RD = [i for i in range(-1, d) if i == -1 or R >> i & 1 == 1]
	else:
		RD = []
	for ld in LD:
		for rd in RD:
			a = 1
			for i in range(d):
				if i < ld and i < rd:
					a *= 3
				if i < ld and i == rd:
					a *= 1
				if i < ld and i > rd:
					a *= (R >> i & 1) + 1
				if i == ld and i < rd:
					a *= 1
				if i == ld and i == rd:
					a *= 0
				if i == ld and i > rd:
					a *= R >> i & 1
				if i > ld and i < rd:
					a *= 2 - (L >> i & 1)
				if i > ld and i == rd:
					if L >> i & 1 == 0:
						a *= 1
					else:
						a *= 0
				if i > ld and i > rd:
					if L >> i & 1 == R >> i & 1:
						a *= 1
					if L >> i & 1 == 0 and R >> i & 1 == 1:
						a *= 1
					if L >> i & 1 == 1 and R >> i & 1 == 0:
						a *= 0
			ans += a
print(ans % (10 ** 9 + 7))


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


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

def __starting_point():
	main()
__starting_point()


import sys
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
mod = 1000000007

def ca(x, y):
	ct = 0
	for i in range(x, y + 1):
		for j in range(i, y + 1):
			if j % i == j ^ i:
				ct += 1
	return ct
ans = 0
(l, r) = na()
dp = [0] * 4
for i in range(60, -1, -1):
	ndp = [0] * 4
	base = 1 << i
	if base <= r and l < base * 2:
		ptn = 0
		if base + 1 <= l:
			ptn += 1
		if r < base * 2 - 1:
			ptn += 2
		ndp[ptn] += 1
	if l >> i != r >> i:
		if l >> i & 1 == 0 and r >> i & 1 == 1:
			ndp[1] += dp[3]
			ndp[2] += dp[3]
	if l >> i & r >> i == l >> i:
		ndp[3] += dp[3]
	if l >> i & 1 == 0:
		ndp[0] += dp[1]
		ndp[1] += dp[1]
	ndp[1] += dp[1]
	if r >> i & 1 == 1:
		ndp[0] += dp[2]
		ndp[2] += dp[2]
	ndp[2] += dp[2]
	ndp[0] += dp[0] * 3
	for k in range(4):
		ndp[k] %= mod
	dp = ndp
print(sum(dp) % mod)


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


import bisect
import collections
import itertools

def getint():
	return int(input())

def getints():
	return list(map(int, input().split()))

def getint2d(rows):
	return [getints() for _ in range(rows)]

def getgrid(rows):
	return [input() for _ in range(rows)]

def array1d(n, value):
	return [value for _ in range(n)]

def array2d(n, m, value):
	return [array1d(m, value) for _ in range(n)]
(min_val, max_val) = getints()

def get_key(pos, is_small, is_large, found):
	return ((pos * 2 + is_small) * 2 + is_large) * 2 + found
mod = 10 ** 9 + 7
cache = [-1] * get_key(64, 1, 1, 1)

def solve(pos, is_small, is_large, found):
	if pos < 0:
		return 1
	key = get_key(pos, is_small, is_large, found)
	res = cache[key]
	if res >= 0:
		return res
	res = 0
	for x in [0, 1]:
		for y in [0, 1]:
			if x == 1 and y == 0:
				continue
			if not is_small and x == 0 and (min_val >> pos & 1 == 1):
				continue
			if not is_large and y == 1 and (max_val >> pos & 1 == 0):
				continue
			if not found and x != y:
				continue
			new_is_small = True if x > min_val >> pos & 1 else is_small
			new_is_large = True if y < max_val >> pos & 1 else is_large
			new_found = True if x == y and x == 1 else found
			res += solve(pos - 1, new_is_small, new_is_large, new_found)
	res = res % mod
	cache[key] = res
	return res
print(solve(63, False, False, False))


from functools import *

@lru_cache(maxsize=None)
def solve(L, R):
	if L > R:
		return 0
	if L == 1:
		return 1 + solve(2, R)
	return solve(L // 2, (R - 1) // 2) + solve((L + 1) // 2, R // 2) + solve((L + 1) // 2, (R - 1) // 2)
print(solve(*map(int, input().split())) % (10 ** 9 + 7))


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


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(list(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]
			elif 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))


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


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)


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


(L, R) = map(int, input().split())
mod = 10 ** 9 + 7
l = '{:060b}'.format(L)
r = '{:060b}'.format(R)
memo = [[[[-1] * 2 for i in range(2)] for j in range(2)] for k in range(60)]

def f(pos, flagL, flagR, flagM):
	if pos == 60:
		return 1
	if memo[pos][flagL][flagR][flagM] != -1:
		return memo[pos][flagL][flagR][flagM]
	ret = 0
	if flagL or l[pos] == '0':
		ret += f(pos + 1, flagL, 1 if r[pos] == '1' else flagR, flagM)
	if flagM and (flagL or l[pos] == '0') and (flagR or r[pos] == '1'):
		ret += f(pos + 1, flagL, flagR, flagM)
	if flagR or r[pos] == '1':
		ret += f(pos + 1, 1 if l[pos] == '0' else flagL, flagR, 1)
	memo[pos][flagL][flagR][flagM] = ret % mod
	return ret % mod
print(f(0, 0, 0, 0) % mod)


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


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


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)


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