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>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
const int MOD = int(1e9) + 7;
int norm(int a) {
	while (a >= MOD)
		a -= MOD;
	while (a < 0)
		a += MOD;
	return a;
}
int mul(int a, int b) {
	return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
	int ans = 1;
	while (k > 0) {
		if (k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}
#define N 201000
int f[N], inf[N];
void precalc() {
	f[0] = inf[0] = 1;
	fore (i, 1, N) {
		f[i] = mul(f[i - 1], i);
		inf[i] = binPow(f[i], MOD - 2);
	}
}
int C(int n, int k) {
	if (k < 0 || n < k)
		return 0;
	return mul(f[n], mul(inf[n - k], inf[k]));
}
int n, l, r;
inline bool read() {
	if(!(cin >> n >> l >> r))
		return false;
	return true;
}
inline void solve() {
	int half = n / 2;
	int st = min(1 - l, r - n);
	int ans = mul(st, C(n, half));
	if (n & 1)
		ans = norm(ans + mul(st, C(n, half + 1)));
	for (int k = st + 1; ; k++) {
		int lf = max(1, l + k);
		int rg = min(n, r - k);
		if (rg + 1 - lf < 0)
			break;
		ans = norm(ans + C(rg + 1 - lf, half - (lf - 1)));
		if (n & 1)
			ans = norm(ans + C(rg + 1 - lf, half + 1 - (lf - 1)));
	}
	cout << ans << endl;
}
int main() {
	precalc();
	int t; cin >> t;
	while (t--) {
		read();
		solve();
	}
	return 0;
}