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;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef pair<double,ll> pdl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<pdd> vdd;
typedef vector<pdi> vdi;
typedef vector<pdl> vdl;
typedef vector<string> vs;
#define fi first
#define se second
const ll INFLL=LLONG_MAX;
const int INF=INT_MAX;
const ll MAXLL=0x3f3f3f3f3f3f3f3f;
const int MAX=0x3f3f3f3f;
const ll MOD=1000000007;
const ll mod=998244353;
#define eb emplace_back
#define emp emplace
#define mp(a,b) make_pair(a,b)
template<class T> using min_heap=priority_queue<T,vector<T>,greater<T> >;
template<class T>
void sort(vector<T>& v){
	sort(v.begin(),v.end());
}
template <class T, class U>
void sort(vector<T>& v,U func){
	sort(v.begin(),v.end(),func);
}
template<class T>
void rsort(vector<T>& v){
	sort(v.rbegin(),v.rend());
}
template <class T>
int lb_index(vector<T>& v,T k){
	return lower_bound(v.begin(),v.end(),k)-v.begin();
}
template <class T>
int ub_index(vector<T>& v,T k){
	return upper_bound(v.begin(),v.end(),k)-v.begin();
}
template<class T>
bool is_sorted(vector<T>& v){
	return is_sorted(v.begin(),v.end());
}
template<class T>
bool sorted(vector<T>& v){
	return is_sorted(v);
}
vl fact(200001),inv(200001);
ll bm(ll b,ll p,ll m){
	if(p==0)return 1;
	if(p&1){
		ll t=bm(b,p>>1,m);
		return ((t*t)%m)*b%m;
	}
	else{
		ll t=bm(b,p>>1,m);
		return (t*t)%m;
	}
}
void precompute(){
	fact[0]=1;
	inv[0]=1;
	for(ll i=1;i<200001;i++){
		fact[i]=fact[i-1]*i;
		fact[i]%=MOD;
//		if(i<100)cout<<fact[i]<<" "<<i<<" \n";
	}
	for(ll i=1;i<200001;i++){
		inv[i]=bm(fact[i],MOD-2,MOD);
//		if(i<100)cout<<inv[i]<<" "<<i<<" \n";
	}
	return;
}
ll ncr(ll n,ll r){
	if(n<0||r<0)return 0;
	if(n<r)return 0;
	return ((fact[n]*inv[r])%MOD*inv[n-r])%MOD;
}
void solve(){
	ll n,l,r;
	cin>>n>>l>>r;
	l=1-l;
	r=r-n;
	ll a=min(l,r);
	ll b=max(l,r);
	b=min(b,a+n-1);
//	n,k
//	k*nC(n/2)
	r=n/2;
	ll ans=0;
	ans=a*ncr(n,r)%MOD;
	if(n&1)ans+=a*ncr(n,r)%MOD;
	ans%=MOD;
//	cout<<ans<<endl;
	for(ll i=1;i<=b-a;i++){
		ans+=ncr(n-i,r);
		ans%=MOD;
		if(n&1)ans+=ncr(n-i,r+1);
		ans%=MOD;
//		cout<<ans<<endl;
	}
//	cout<<"OK\n";
	for(int i=1;;i++){
		ans+=ncr(n-(b-a)-i-i,r-i);
		ans%=MOD;
		if(n&1)ans+=ncr(n-(b-a)-i-i,r-i+1);
		ans%=MOD;
//		cout<<ans<<endl;
		if(ncr(n-(b-a)-i-i,r-i)==0)break;
	}
	cout<<ans<<endl;
	return;
}

int main(){
	ios::sync_with_stdio(0);
	int numberofsubtestcases=1;
	cin>>numberofsubtestcases;
	precompute();
	for(int looping=1;looping<=numberofsubtestcases;looping++){
//		cout<<"Case #"<<looping<<": ";
		solve();
	}
	return 0;
}


