TOURNAMENT

Problem

In an online billiards championship, each player plays against various other players in the order determined by the system. Each win earns the player some points, and these points are accumulated for each player - losses, on the other hand, do not give points. To make the game more interesting, the organizers of the championship have decided on the following evaluation system:

• The points for each win increase according to the number of consecutive wins achieved by a player. The first win gives ~1~ point, the second (consecutive) ~2~ points, the third (again consecutive) ~4~ points, the fourth ~8~ points, and so on.
• In case of a loss, consecutive wins naturally end. Thus, the first subsequent win will again give ~1~ point.
• If a player loses two consecutive times, they are eliminated from the championship.

Let there be two natural numbers ~A \le B~. Find in how many different ways a player can accumulate ~K~ points, where ~A \le K \le B~, before being eliminated from the championship.

For example, if ~A = 2~ and ~B = 4~, a player can accumulate ~2~, ~3~, or ~4~ points in the following twelve (~12~) ways, where the numbers denote a win that gives as many points as the value of the number, and the symbol ~x~ denotes a loss:

1 x 1 x x                        1 x 1 2 x x 
x 1 x 1 x x                      x 1 x 1 2 x x 
1 x 1 x 1 x x                    1 2 x x 
x 1 x 1 x 1 x x                  x 1 2 x x 
1 x 1 x 1 x 1 x x                1 2 x 1 x x 
x 1 x 1 x 1 x 1 x x              x 1 2 x 1 x x

Input:

The first line of the input will contain an integer ~N~, the number of queries you need to answer. Each of the next ~N~ lines of the input will contain two numbers ~A~ and ~B~, separated by a space.

Output:

The output should consist of exactly ~N~ lines, each containing exactly one integer: the answer to the corresponding query in order. Because the answer can be a very large number for large values of ~A~ and ~B~, you should print the remainder (modulo) of this number divided by ~10^9 + 7~.

Constraints

• ~1 \le N \le 1.000.000~
• ~0 \le A \le B \le 1.000.000~
• Time limit: ~2~ sec.
• Memory limit: ~128~ MB.

Attention: Both the size of the input data and the size of the output data can be large. We recommend reading the data efficiently (see <cstdio> and scanf).

Notes

• For test cases with a total value of ~20%~, it will be ~N \le 1000~ and ~B \le 30~.
• For test cases with a total value of ~50%~, it will be ~N \le 10.000~ and ~B \le 100.000~.
• For test cases with a total value of ~60%~, it will be ~B - A \le 10~.

Example of Input - Output Files:

STDIN (tournament.in)

4
2 4
3 3
17 42
1742 4217

STDOUT (tournament.out)

12
4
126321690
376826466

Explanation of the example

The first query, with ~A = 2~ and ~B = 4~, is the one explained in detail above.