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 int long long
vector<int>fact(2000010);
vector<int>inv(2000010);
const int mod = (int)1e9+7;
int modpow(int x, int y) {
	return !y?1:((y % 2 ? x : 1) * modpow((x * x) % mod, y / 2)) % mod;
}
int choose(int x, int y){
	if(y>x)return 0;
	if(y<0||x<0)return 0;
	return (fact[x]*inv[y]%mod)*inv[x-y]%mod;
}
int permute(int x, int y){
	if(y>x)return 0;
	return (fact[x]*inv[x-y])%mod;
}
void precalc(){
	fact[0] = 1; inv[0] = 1;
	for(int i = 1; i<=2000000; i++){
		fact[i] = fact[i-1]*i%mod;
	}
	inv[2000000] = modpow(fact[2000000],mod-2);
	for(int i = 1999999; i>0; i--){
		inv[i] = inv[i+1]*(i+1)%mod;
	}
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false); precalc();
	int t;
	cin >> t;
	while(t--){
		int n,l,r;
		cin >> n >> l >> r;
		if(abs(l-1)<r-n){
			int temp = 1-(r-n);
			r = n+abs(l-1);
			l = temp;
		}
		//cout << l << " " << r << " " << "\n";
		int x = 1;
		if(r-n>0){
			x = r-n;
		}
		if(abs(l-1)>0){
			x = min(x,abs(l-1));
		}
		int ans = (x-1)*choose(n,n/2)%mod;
		if(n%2==1)ans+=(x-1)*choose(n,n/2+1)%mod;
		ans%=mod;
		int left = 0; int right = n+1;//left and right mean that the first (left value) amount of values in the array are too small or too big to subtract or add x
		//cout << ans << " " << x << "\n";
		while(left<=n&&right>=1){
			while(left-x<l-1){
				left++;	
			}
			while(right+x>r+1){
				right--;
			}
			//cerr << left << " " << right << " " << x << "\n";
			int rem = right-left-1;
			ans+=choose(rem,n/2-left);
			ans%=mod;
			if(n%2==1)ans+=choose(rem,n/2+1-left);
			ans%=mod;
			x++;
		}
		cout << ans << "\n";
	}
	return 0;
}