B. Adhoom and Halzoom Peculiar Pact
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Having navigated the treacherous Spirit-Oak Grove, the three found their path leading to a quaint, dilapidated mill. Inside, they found two eccentric figures: Adham, a gruff but jovial miller with flour perpetually dusting his beard, and his perpetually bewildered apprentice, Halzoom.

It seemed Adham and Halzoom had a long-standing tradition of challenging each other with cryptic number puzzles. This time, Adham, having just won their latest bout, decided to present Halzoom with a particularly fiendish one, but it immediately caught Sam07a's strategic eye.

"Listen closely, Halzoom!" Adham bellowed, tapping a chalk-dusted finger on a grimy chalkboard. "Given two incredibly large numbers, $$$L$$$ and $$$R$$$, you must count the number of ordered pairs of integers $$$(a,b)$$$ that satisfy these precise conditions:"

  • $$$(L \le a \le b \le R)$$$
  • $$$b \bmod a = b + a - 2 \cdot (a \,\&\, b)$$$ (where "&" denotes the bitwise AND operation)

Halzoom scratched his head, already looking overwhelmed. But Abd-Elmohaymen, recognizing a deep mathematical challenge, nudged Sam07a. "This sounds like something the Old Man of the Woods would set! If we solve it for them, perhaps they'll show us the way to the Whispering Bridge." Abd-Elmohaymen, meanwhile, was fascinated by the bitwise AND operation, wondering what strange magic it might represent.

The answer to such a puzzle could be astronomically large, so Adham added a final, critical instruction: "Since the answer can be very large, present it modulo $$$10^9 +7$$$ !"

Help Sam07a, Omar, and Abd-Elmohaymen solve Adham and Halzoom's perplexing problem to earn their passage through the mill.

Input

Two integers $$$L$$$ , $$$R$$$ $$$(1\leq L \leq R \leq 10^{18})$$$

Output

Print the number of ordered pairs of integers $$$(a , b)$$$ that meet both the condition modulo $$$10^9 + 7$$$.

Example
Input
5 9
Output
8