beecrowd | 2363
# Playing with Transformations

**Timelimit: 1**

By Lucas Maciel, UFMG Brazil

Luiz is a very strange boy from Syldavia. He really loves play with sequences of integer numbers. Tired of playing with the same sequence (from 1 to **N**), Luiz proposed some transformations.:

*EVEN(S)*and*ODD(S)*are two transformations that filter even or odd positions of any sequence S, returning a new sequence*REC(S) = REC(EVEN(S)) + REC(ODD(S))*. This recursive transformation concatenate two sequences according with the operator ( + ), filtering both with the previous transformations.

As the sequences could be so large, Luiz only want know the sum of some interval **[A, B]** modulo 10^{9}+7.

**Observations**

*REC(S) = S* for *|S| = 1*, ie. if some sequence has only one element, *REC* of its sequence is itself.

The input consists of many test cases. Each test case has three integers **N, A** and **B** that represent the size of the original sequence (from 1 to N), and the interval **[A, B]** of the *REC* transformation in the original sequence that want to know the sum. (1 ≤ **A** ≤ **B** ≤ **N** ≤ 10^{18}).

For each test case, output the sum modulo 10^{9}+7.

Input Sample | Output Sample |

5 2 4 |
10 |

In the first case, initially Luiz has a sequence *S = {1, 2, 3, 4, 5}*. Let *S _{1} = EVEN(S) = {2, 4}* e