Let's call an integer array a_1, a_2, ..., a_n good if a_i ≠ i for each i.

Let F(a) be the number of pairs (i, j) (1 ≤ i < j ≤ n) such that a_i + a_j = i + j.

Let's say that an array a_1, a_2, ..., a_n is excellent if: 

  * a is good; 
  * l ≤ a_i ≤ r for each i; 
  * F(a) is the maximum possible among all good arrays of size n. 



Given n, l and r, calculate the number of excellent arrays modulo 10^9 + 7.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. 

The first and only line of each test case contains three integers n, l, and r (2 ≤ n ≤ 2 ⋅ 10^5; -10^9 ≤ l ≤ 1; n ≤ r ≤ 10^9).

It's guaranteed that the sum of n doesn't exceed 2 ⋅ 10^5.

Output

For each test case, print the number of excellent arrays modulo 10^9 + 7.

Example

Input


4
3 0 3
4 -3 5
42 -33 55
69 -42 146


Output


4
10
143922563
698570404

Note

In the first test case, it can be proven that the maximum F(a) among all good arrays a is equal to 2. The excellent arrays are: 

  1. [2, 1, 2]; 
  2. [0, 3, 2]; 
  3. [2, 3, 2]; 
  4. [3, 0, 1]. 
import java.io.*;
import java.util.*;


public class edu111p4 {
	public static void main(String[] args) throws IOException {
		//BufferedReader br = new BufferedReader(new FileReader(new File("input.txt")));
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    // read line
	    long p = 1000000007;
	    long[] fac = new long[200002];
	    fac[0] = 1;
	    for(int i = 1; i < 200001; i++) {
	    	fac[i] = (i * fac[i-1]) % p;
	    }
	    
	    int t = Integer.parseInt(br.readLine());
	    // read thing-by-thing
	    for(int i = 0; i < t; i++) {
		    StringTokenizer st = new StringTokenizer(br.readLine());
		    long n = Integer.parseInt(st.nextToken());
		    long l = Integer.parseInt(st.nextToken());
		    long r = Integer.parseInt(st.nextToken());
		    int k = (int) (n/2);
		    int k2 = (int) ((n+1)/2);
		    long count = 0;
		    long start = Math.min(1-l, r-n) % p;
		    count += ((((start%p) * fac[2*k2]%p)%p) * (((inverse(fac[k2],p)  * inverse(fac[k2],p))%p)%p))%p;
		    count = count % p;
		    for(int j =  1; j <= n-k; j++) {
		    	int a = (int) Math.min(n, n-(l-1+start)-j);
		    	int b = (int) Math.min(n, (r-start)-j);
		    	if(a+b >= n) {
		    		count += ( ((fac[a+b-2*k] * inverse(fac[a-k],p)) %p) * inverse(fac[b-k],p) )%p;
		    		count = count % p;
		    	}
		    }
		    System.out.println(count);
	    }
	    br.close();
	}
	
	

	
	public static long inverse(long a, long p) {
		return power(a,p-2,p);
	}
	
	static long power(long x, long y, long m)
    {
        if (y == 0)
            return 1;
        long p = power(x, y / 2, m) % m;
        p = (int)((p * (long)p) % m);
        if (y % 2 == 0)
            return p;
        else
            return (int)((x * (long)p) % m);
    }
}