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 <bits/stdc++.h>

#define int long long

#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);

#ifdef PICHU_LOCAL_DEF
	#include <chrono>
#endif

using namespace std;

const int MOD = 1e9 + 7, MAXN = 3e5 + 5;

int n, l, r;
int fact[MAXN], inv[MAXN];

int power(int x, int n) {
	int res = 1;
	while (n) {
		if (n & 1) (res *= x) %= MOD;
		(x *= x) %= MOD;
		n >>= 1;
	}
	return res;
}

int inverse(int x) {
	return power(x, MOD - 2);
}

int C(int n, int k) {
	if (n < k) return 0;
	return fact[n] * inv[n - k] % MOD * inv[k] % MOD;
}

bool check(int x, int a, int b) {
	int left = max(l + x, 1ll), right = min(r - x, n);
	int p = left - 1, q = right - left + 1, rp = n - right;
	bool bb = 1;

	if (rp + q < b || p + q < a) bb = 0;

	return bb;
}

int ssolve(int a, int b) {
	// a (i - x), b (i + x)
	int ans = 0;

	// for (int x = 1; x <= 1e5; x++) {

	// 	if (l + x > r - x + 1) continue;

		// if (n - x > r) continue;
		// if (1 + x < l) continue;

	// 	if (r + q < b || p + q < a) continue;

	// 	ans += C(q, b - rp);

	// 	ans %= MOD;
	// }

	// n - x <= r => x >= n - r
	// 1 + x >= l => x >= l - 1

	int lb = max(n - r, l - 1);
	lb = max(lb, 1ll);

	int ll = lb, rr = 2e9;

	while (ll < rr) {
		int x = (ll + rr + 1) >> 1;

		if (check(x, a, b)) ll = x;
		else rr = x - 1;
	}

	if (!check(lb, a, b)) return 0;

	int md = -1;

	for (int x = ll; x >= lb; x--) {
		int left = max(l + x, 1ll), right = min(r - x, n);

		int p = left - 1, q = right - left + 1, rp = n - right;
		
		// cout << x << ' ' << p << ' ' << q << ' ' << rp << '\n';

		if (q == n) {
			md = x;
			break;
		}
		ans += C(q, b - rp);

		ans %= MOD;
	}

	if (md != -1) (ans += C(n, b) * (md - lb + 1)) %= MOD; 

	return ans;
}

void solve() {
	cin >> n >> l >> r;

	int vv = n / 2;
	if (n % 2 == 0) 
		cout << ssolve(vv, vv) << '\n';
	else cout << (ssolve(vv, n - vv) + ssolve(n - vv, vv)) % MOD << '\n';
}


signed main() {
	#ifdef PICHU_LOCAL_DEF
		chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
	#endif

	#ifndef PICHU_LOCAL_DEF
		//fileopen1("LAH");
	#endif

	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	fact[0] = 1;
	for (int i = 1; i < MAXN; i++) fact[i] = fact[i - 1] * i % MOD;
	for (int i = 0; i < MAXN; i++) inv[i] = inverse(fact[i]);

	int t = 1;
	cin >> t;
	while (t--) solve();

	#ifdef PICHU_LOCAL_DEF
		chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
		std::cout << std::endl;
		std::cout << "Time difference = " << chrono::duration_cast<chrono::milliseconds> (end - begin).count() << "[ms]" << std::endl;
	#endif
}

