A non-decreasing sequence is a called a Fox sequence, iff the most frequent element in the sequence is unique.

e.g. The sequence 1, 1, 2, 3, 4 is a Fox sequence, because it follows the above definition. The most frequent element is 1. It occurs twice in the series, and is unique.

But the sequence 1, 1, 2, 2 is not a Fox sequence, because there are two most frequent elements - 1 and 2. It violates the uniqueness property.

Note: Sequence 2, 1, 1 is not a Fox sequence, because it is not a non-decreasing sequence.

You need to find the number of all possible Fox sequences of length n with elements having value between lo and hi inclusive.

As the number can grow very large, return the number modulo (10^{9} + 7).

Input Format

The first line will contain T, i.e., the number of test cases.

For each test case, there will be a single line containing three space separated integers n, lo, hi.

Output Format

For each test case, display a single value corresponding to the number of all possible Fox sequences.

Constraints

1 ≤ T ≤ 5

1 ≤ lo, hi ≤ 10^{9}

lo ≤ hi

0 ≤ |hi - lo| < 10^{5}

1 ≤ n ≤ 10^{5}

Sample Input

5
2 1 1
2 1 3
3 1 2
4 4 5
10 2 4

Sample Output

1
3
4
4
60

Explanation

For the first test case, 1 1 is the only possible Fox sequence.

For the second test case, 1 1, 2 2, and 3 3 are three possible Fox sequences.

For the third test case, 1 1 1, 2 2 2, 1 1 2, and 1 2 2 are four possible Fox

sequences.

Rest of the test cases are up to you to figure out.

见题面

见题面