bee 2363 - Playing with Transformations

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⁹+7.

Observations

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

Input

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¹⁸).

Output

For each test case, output the sum modulo 10⁹+7.

Input Sample	Output Sample
5 2 4 1000000000 1 1000000000	10 21

In the first case, initially Luiz has a sequence S = {1, 2, 3, 4, 5}. Let S₁ = EVEN(S) = {2, 4} e S₂ = ODD(S) = {1, 3, 5}, then REC(S) = REC(S₁) + REC(S₂). Calculating REC(S₁) we need first calculate EVEN(S₁) = {4} and ODD(S₁) = {2}. As REC({4}) = {4} and REC({2}) = {2}, so REC(S₁) = {4, 2}. Now, let us calculate REC(S₂). To do that, let S_2₁ = EVEN(S₂) = {3} and S_2₂ = ODD(S₂) = {1, 5}, then REC(S_2₁) = {3} and as you probably noticed, REC(S_2₂) = {5, 1}. So, REC(S₂) = {3, 5, 1}. Therefore, REC(S) = REC(S₁) + REC(S₂) = {4, 2} + {3, 5, 1} = {4, 2, 3, 5, 1}. And because we want know the sum from second to fourth elements ([2, 4]), then we do 2 + 3 + 5 = 10.