Sunny has developed chronic depression from implementing Pascal as a submission language in WYKOJ. He despises Pascal so much that he recently created a pull request to remove Pascal from WYKOJ entirely.

One day, Sunny stumbled upon Pascal's triangle in his M2 class. Pascal's triangle is constructed by summing adjacent elements in preceding rows. Note that the topmost row is the $ 0 $th row.

Just as he was about to drop M2 for his hatred for Pascal, he discovered a shocking fact about Pascal's triangle:

Indeed, the sum of all elements on the $ n $th row is $ 2^n $. Consider the $ 3 $rd row: $ 1 + 3 + 3 + 1 = 8 = 2^3 $. It seems that Sunny's depression has been cured by this amazing fact.

Now, Sunny is thinking about the sum of consecutive rows in Pascal's triangle. Help Sunny find the sum of all elements from row $ a $ up to row $ b $, modulo $ 10^9+7 $.

Hint

The sum of all elements on the $ n $th row is $ 2^n $, which is $ 1 \underbrace{0 \ldots 00}_{n \text{ zeros}} $ in binary.

Input

The only line of input consists of two integers $ a $ and $ b $.

Output

Output the required sum modulo $ 10^9+7 $.

Constraints

Subtask 1 (30%): $ 0 \le a \le b \le 10^3 $
Subtask 2 (30%): $ 0 \le a \le b \le 10^6 $
Subtask 3 (40%): $ 0 \le a \le b \le 10^9 $