It is summers, the season of Mangoes, in MangoLand. Mr. Even has landed himself in a serious trouble by gobbling up too many mangoes. He has been diagnosed with Disparnumerophobia (the fear of Odd numbers). The doctors in MangoLand are unable to cure him.

To cure Mr. Even of this dreaded disease, Dr Prime and Dr Modulo are called in from MathLand. Dr Prime suggests Mr. Even to distribute mangoes in MangoLand starting with distributing exactly 1 mango (since 1 is the smallest odd number) to each of the first two houses he visits. There are $N$ houses in MangoLand. Each house is numbered from 1 to $N$. To each of the next houses, Mr. Even should distribute Mangoes such that the number of mangoes received by the house is equal to the sum of the mangoes received by the previous two houses (in the ordering 1 to $N$).

Dr Modulo will then test if Mr. Even is fully cured of his disease. He will test Mr. Even $T$ times, each time with different values of $N$, $L$ and $R$. Dr Modulo sees that some houses receive odd number of mangoes while others receive even number of mangoes. So, he just requires the sum of the number of mangoes distributed to those houses which received an odd number of mangoes between $L^{th}$and $R^{th}$ (both inclusive) houses. Since, Mr. Even is quite forgetful, he asks you for help. Dr Modulo is in love with primes (Dr Prime too). He has special liking for the prime $10^9+7$. So, please output the answer modulo $10^9+7$ . If you don’t help Mr. Even, he might get affected with Phobophobia (the fear of phobias). So, we request you to help him.

Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains an integer N, denoting the number of houses in MangoLand.
• The second line contains two space-separated integers L and R.
• Note : The Input files are large.

Output

For each test case, print a single line containing one integer — the sum of number of mangoes received by those houses which received an odd number of mangoes modulo $10^9+7$.

Constraints

• $1\le T \le 10^5$
• $1\le N \le 10^{18}$
• $1\le L \le R\le N$

Problem Setter: Ankit Kumar Singh