Kabir wants to impress Tara by showing her his problem solving skills. He has decided to give the correct answer to the next question which will be asked by his Algorithms teacher.
The question asked is:
Find the sum of alternate consecutive d$d$ odd numbers from the range L$L$ to R$R$ inclusive.
if d$d$ is 3 and L$L$ is 10 and R$R$ is 34, then the odd numbers between 10 and 34 are 11,13,15,17,19,21,23,25,27,29,31,33$11,13,15,17,19,21,23,25,27,29,31,33$, and the d$d$ alternate odd numbers are 11,13,15,23,25,27$11,13,15,23,25,27$.
You are a friend of Kabir, help him solve the question.
Note:$Note:$ Number of odd number between L$L$ and R$R$ (both inclusive) is a multiple of d$d$.

-----Input:-----
- First line will contain T$T$, number of test cases.
- First line of each test case contains one integer d$d$ .
- Second line of each test case contains two space separated integer L$L$ and R$R$.

-----Output:-----
For each test case, print the sum modulo 1000000007.

-----Constraints:-----
- 1≤T≤106$1 \leq T \leq 10^6$
- 1≤d≤103$1 \leq d \leq 10^3$
- 1≤L<R≤106$1 \leq L < R \leq 10^6$

-----Sample Input:-----
1
3

10 33

-----Sample Output:-----
114

-----EXPLANATION:-----
Sum of alternate odd numbers i.e, 11,13,15,23,25,27 is 114

见题面

见题面