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.util.*;
import java.io.*;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.Math.max;
public class EdC {
	static long[] mods = {1000000007, 998244353, 1000000009};
	static long mod = mods[0];
	static long[] fact;
	public static MyScanner sc;
    public static PrintWriter out;
	public static void main(String[] largewang) throws Exception{
		// TODO Auto-generated method stub
		fact = new long[200001];
		fact[0] = 1;
		for(int j = 1;j<=200000;j++){
			fact[j] = j*fact[j-1];
			fact[j] %= mod;
		}
 		sc = new MyScanner();
 		out = new PrintWriter(System.out);
 		int t = sc.nextInt();
 		while (t-->0) {
 			int n = sc.nextInt();
 			long l = sc.nextLong();
 			long r = sc.nextLong();
 			long ans = ((int)max(1, min(1-l, r-n)) - 1);
 			ans %= mod;
 			ans *= binom(n, n/2);
 			ans %= mod;
 			
 			if (n%2 == 1){
 				ans *=2L;
 				ans %= mod;
 			}
 			for(int x = (int)max(1, min(1-l, r-n));x<=max(1, min(1-l, r-n))+n;x++){
 				if (n%2 == 0){
 					// n/2 +x's n/2 -x's
 					long val = l+x;
 					long numBelow = max(0, min(l+x-1, n));
 					long val2 = r-x;
 					long numAbove = max(0, min(n-r+x, n));
 					
 					int numPos = n/2;
 					int numNeg = n/2;
 					
 					numPos-= (int)numBelow;
 					numNeg-= (int)numAbove;
 					if (numPos >=0 && numNeg >=0){
 						ans += binom(numPos+numNeg, numPos);
 						ans %= mod;
 					}
 				} else {
 					// n/2 +x's (n+1)/2 -x's
 					//or
 					// (n+1)/2 +x's n/2 -x's
 					long val = l+x;
 					long numBelow = max(0, min(l+x-1, n));
 					long val2 = r-x;
 					long numAbove = max(0, min(n-r+x, n));
 					
 					int numPos = n/2;
 					int numNeg = (n+1)/2;
 					
 					numPos-= (int)numBelow;
 					numNeg-= (int)numAbove;
 					if (numPos >=0 && numNeg >=0){
 						ans += binom(numPos+numNeg, numPos);
 						ans %= mod;
 					}
 					
 					numPos = (n+1)/2;
 					numNeg = n/2;
 					
 					numPos-= (int)numBelow;
 					numNeg-= (int)numAbove;
 					if (numPos >=0 && numNeg >=0){
 						ans += binom(numPos+numNeg, numPos);
 						ans %= mod;
 					}
 				}
 			}
 			out.println(ans);
 			
 		}
 		out.close();
 		
 	}
	public static long inv(long n){
		return power(n, mod-2);
	}
	public static long binom(int n, int k){
		long prod = fact[n];
		prod*=inv(fact[n-k]);
		prod%=mod;
		prod*=inv(fact[k]);
		prod%=mod;
		return prod;	
	}
	public static void sort(int[] array){
		ArrayList<Integer> copy = new ArrayList<>();
		for (int i : array)
			copy.add(i);
		Collections.sort(copy);
		for(int i = 0;i<array.length;i++)
			array[i] = copy.get(i);
	}
	static String[] readArrayString(int n){
		String[] array = new String[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.next();
		return array;
	}
	static int[] readArrayInt(int n){
    	int[] array = new int[n];
    	for(int j = 0;j<n;j++)
    		array[j] = sc.nextInt();
    	return array;
    }
	static int[] readArrayInt1(int n){
		int[] array = new int[n+1];
		for(int j = 1;j<=n;j++){
			array[j] = sc.nextInt();
		}
		return array;
	}
	static long[] readArrayLong(int n){
		long[] array = new long[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextLong();
		return array;
	}
	static double[] readArrayDouble(int n){
		double[] array = new double[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextDouble();
		return array;
	}
	static int minIndex(int[] array){
		int minValue = Integer.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(long[] array){
		long minValue = Long.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(double[] array){
		double minValue = Double.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static long power(long x, long y){
		if (y == 0)
			return 1;
		if (y%2 == 1)
			return (x*power(x, y-1))%mod;
		return power((x*x)%mod, y/2)%mod;
	}
	static void verdict(boolean a){
        out.println(a ? "YES" : "NO");
    }
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } 
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try{
                str = br.readLine();
            } 
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
    }	
}

//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is