beecrowd | 2363

# Playing with Transformations

By Lucas Maciel, UFMG Brazil

Timelimit: 1

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 109+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 ≤ ABN ≤ 1018).

## Output

For each test case, output the sum modulo 109+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 S1 = EVEN(S) = {2, 4} e S2 = ODD(S) = {1, 3, 5}, then REC(S) = REC(S1) + REC(S2). Calculating REC(S1) we need first calculate EVEN(S1) = {4} and ODD(S1) = {2}. As REC({4}) = {4} and REC({2}) = {2}, so REC(S1) = {4, 2}. Now, let us calculate REC(S2). To do that, let S21 = EVEN(S2) = {3} and S22 = ODD(S2) = {1, 5}, then REC(S21) = {3} and as you probably noticed, REC(S22) = {5, 1}. So, REC(S2) = {3, 5, 1}. Therefore, REC(S) = REC(S1) + REC(S2) = {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.