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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Practice {
	public static long mod = (long) Math.pow(10, 9) + 7;
	public static long mod2 = 998244353;
	public static int tt = 1;
	public static ArrayList<Integer> prime;
	public static long[] fac = new long[200005];
	public static long[] invfac = new long[200005];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		int t = Integer.parseInt(br.readLine());
		// int c = 1;

		for (int i = 0; i < fac.length; i++) {
			if (i == 0) {
				fac[i] = 1;
			} else {
				fac[i] = (i * fac[i - 1]) % mod;
			}
		}

		for (int i = 0; i < fac.length; i++) {
			long no = fac[i];
			invfac[i] = power(no, mod - 2);
		}

		while (t-- > 0) {
			String[] s1 = br.readLine().split(" ");
			int n = Integer.parseInt(s1[0]);
			long l = Long.valueOf(s1[1]);
			long r = Long.valueOf(s1[2]);
			long ans = 0;
			long all = Math.min(r - n, -(l - 1));
			if (n % 2 == 0) {
				ans = (Math.min(r - n, -(l - 1)) * ncr(n, n / 2)) % mod;
			} else {
				ans = (2 * (Math.min(r - n, -(l - 1)) * ncr(n, n / 2)) % mod) % mod;
			}
			// System.out.println(ans + " " + all);
			for (int i = 0; i < n; i++) {
				long no = all + i + 1;
				int pos = (int) Math.min(n, r - no);
				int neg = (int) Math.min(n, -no - (l - n) + 1);
				if (pos < 0 || neg < 0) {
					break;
				}

				int dono = pos + neg - n;
				pos -= dono;
				neg -= dono;
				if (pos + neg + dono != n || pos > (n + 1) / 2 || neg > (n + 1) / 2) {
					break;
				}
				if (n % 2 == 1) {
					ans = (ans + ncr(dono, n / 2 - pos)) % mod;
					ans = (ans + ncr(dono, (n) / 2 - neg)) % mod;
				} else {
					ans = (ans + ncr(dono, n / 2 - pos)) % mod;
				}
			}
			pw.println(ans);
		}

		pw.close();
	}

	private static long ncr(int n, int r) {
		if (n < r || n < 0 || r < 0) {
			return 0;
		}
		// TODO Auto-generated method stub
		return (((fac[n] * invfac[r]) % mod) * invfac[n - r]) % mod;
	}

	private static long power(long a, long p) {
		// TODO Auto-generated method stub
		long res = 1;
		while (p > 0) {
			if (p % 2 == 1) {
				res = (res * a) % mod;
			}
			p = p / 2;
			a = (a * a) % mod;
		}
		return res;
	}

//	private static int kmp(String str) {
//		// TODO Auto-generated method stub
//		// System.out.println(str);
//		int[] pi = new int[str.length()];
//		pi[0] = 0;
//		for (int i = 1; i < str.length(); i++) {
//			int j = pi[i - 1];
//			while (j > 0 && str.charAt(i) != str.charAt(j)) {
//				j = pi[j - 1];
//			}
//			if (str.charAt(j) == str.charAt(i)) {
//				j++;
//			}
//			pi[i] = j;
//			System.out.print(pi[i]);
//		}
//		System.out.println();
//		return pi[str.length() - 1];
//	}

}

//	private static void getFac(long n, PrintWriter pw) {
//		// TODO Auto-generated method stub
//		int a = 0;
//		while (n % 2 == 0) {
//			a++;
//			n = n / 2;
//		}
//		if (n == 1) {
//			a--;
//		}
//		for (int i = 3; i <= Math.sqrt(n); i += 2) {
//			while (n % i == 0) {
//				n = n / i;
//				a++;
//			}
//		}
//		if (n > 1) {
//			a++;
//		}
//		if (a % 2 == 0) {
//			pw.println("Bob");
//		} else {
//			pw.println("Alice");
//		}
//		//System.out.println(a);
//		return;
//	}

//	private static long power(long a, long p) {
//		// TODO Auto-generated method stub
//		long res = 1;
//		while (p > 0) {
//			if (p % 2 == 1) {
//				res = (res * a) % mod;
//			}
//			p = p / 2;
//			a = (a * a) % mod;
//		}
//		return res;
//	}
//
//	private static void fac() {
//		fac[0] = 1;
//		// TODO Auto-generated method stub
//		for (int i = 1; i < fac.length; i++) {
//			if (i == 1) {
//				fac[i] = 1;
//			} else {
//				fac[i] = i * fac[i - 1];
//			}
//			if (fac[i] > mod) {
//				fac[i] = fac[i] % mod;
//			}
//		}
//	}
//
//	private static int getLower(Long long1, Long[] st) {
//		// TODO Auto-generated method stub
//		int left = 0, right = st.length - 1;
//		int ans = -1;
//		while (left <= right) {
//			int mid = (left + right) / 2;
//			if (st[mid] <= long1) {
//				ans = mid;
//				left = mid + 1;
//			} else {
//				right = mid - 1;
//			}
//		}
//		return ans;
//	}

//	private static long getGCD(long l, long m) {
//
//		long t1 = Math.min(l, m);
//		long t2 = Math.max(l, m);
//		while (true) {
//			long temp = t2 % t1;
//			if (temp == 0) {
//				return t1;
//			}
//			t2 = t1;
//			t1 = temp;
//		}
//	}