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]. 
#include "stdio.h" 
#include "algorithm" 
#include "stdlib.h" 
#include "set" 
#include "map" 
#include "queue" 
#include "vector"
#include "math.h" 
#include "stack" 
#include "time.h" 

// #include "bits/stdc++.h"

// #define int long long


int Max(int a, int b) {
	return a > b? a: b; 
}
int Min(int a, int b) {
	return a < b? a: b; 
}
int Abs(int a) {
	return a < 0? -a: a; 
}
int sqr(int a) {
	return (long long)a * a; 
}
int qpow(int a, int b) {
	if (b < 0) 
		return 0; 
	int ans = 1; 
	while (b) {
		if (b & 1) 
			ans = 1ll * a * ans % 1000000007; 
		a = 1ll * a * a % 1000000007; 
		b >>= 1; 
	}
	return ans; 
}

// #undef int

int T; 
int n, l, r; 
int a[200010]; 
long long ans; 
int fac[200010], invfac[200010]; 
const int mod = 1000000007; 

int C(int m, int n) {
	return 1ll * fac[n + m] * invfac[m] % mod * invfac[n] % mod; 
}

int main() {
	scanf("%d", &T); 
	// T = 1; 
	fac[0] = fac[1] = invfac[0] = invfac[1] = 1; 
	for (int i = 2; i <= 200000; ++ i) 
		fac[i] = 1ll * i * fac[i - 1] % mod, invfac[i] = 1ll * (mod - mod / i) * invfac[mod % i] % mod; 
	for (int i = 2; i <= 200000; ++ i) 
		invfac[i] = invfac[i] * 1ll * invfac[i - 1] % mod; 
	while (T --) {
		ans = 0; 
		int mx = 2147483647, mxx = 2147483647; 
		scanf("%d", &n); 
		scanf("%d%d", &l, &r); 
		for (int i = 1; i <= n; ++ i) 
			mx = Min(mx, Max(i - l, r - i)), mxx = Min(mxx, Min(i - l, r - i)); 
		// printf("%d %d\n", mx, mxx); 
		for (int x = mxx + 1; x <= mx; ++ x) {
			int aa = Max(0, Min(n, n - (x + l) + 1)), bb = Max(0, Min(n, r - x)), cc = Max(0, Min(aa, Min(bb, r - x - (x + l) + 1))); 
			if (Max(aa - cc, bb - cc) > Max(n / 2, n - n / 2)) 
				break; 
			(ans += 1ll * C(n / 2 - (aa - cc), n - n / 2 - (bb - cc))) %= 1000000007; 
			if (n & 1) 
				(ans +=  C(n - n / 2 - (aa - cc), n / 2 - (bb - cc))) %= mod; 
			// printf("%d %d %d\n", aa, bb, cc); 
		}
		ans += 1ll * mxx * C(n / 2, n - n / 2) % 1000000007; 
		if (n & 1) 
			ans += 1ll * mxx * C(n - n / 2, n / 2) % mod; 
		printf("%lld\n", ans % 1000000007); 
	}
	// #ifndef ONLINE_JUDGE 
	// 	while (1); 
	// #endif 
}

/*
(a^b) & c = a&c ^ b&c = c
*/