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 long double ld;
const long double eps=0;
//TIAS MONDAL
 
const ll maxn=2e5+10;
const ll mod=1e9+7;
const ll m2=1e9+7;
const ll INF64 = ll(1e18);
const ll max2=1e3+10;
const ll N = 1000001;
const ll MAXN=2e5+10;
const ll ALPHABET_SIZE = 2;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

// array to store inverse of 1 to N
ll factorialNumInverse[N + 1];
 
// array to precompute inverse of 1! to N!
ll naturalNumInverse[N + 1];
 
// array to store factorial of first N numbers
ll fact[N + 1];
 
// Function to precompute inverse of numbers
void InverseofNumber(ll p)
{
    naturalNumInverse[0] = naturalNumInverse[1] = 1;
    for (ll i = 2; i <= N; i++)
        naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
}
// Function to precompute inverse of factorials
void InverseofFactorial(ll p)
{
    factorialNumInverse[0] = factorialNumInverse[1] = 1;
 
    // precompute inverse of natural numbers
    for (ll i = 2; i <= N; i++)
        factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
}
 
// Function to calculate factorial of 1 to N
void factorial(ll p)
{
    fact[0] = 1;
 
    // precompute factorials
    for (ll i = 1; i <= N; i++) {
        fact[i] = (fact[i - 1] * i) % p;
    }
}
 
// Function to return nCr % p in O(1) time
ll nCr(ll N, ll R, ll p)
{
    // n C r = n!*inverse(r!)*inverse((n-r)!)
    ll ans = ((fact[N] * factorialNumInverse[R])
              % p * factorialNumInverse[N - R])
             % p;
    return ans;
}
ll pos(ll l,ll r,ll b,ll n)
{	if(l<0 || r<0 || b<0)
	return(0);
	if(l>(n+1)/2)
	{
		return(0);
	}
	if(r>(n+1)/2)
		return(0);
	if(l==(n+1)/2)
	{
		if(b+r==n-(n+1)/2)
			return(1);
		return(0);
	}
	else if(r==(n+1)/2)
	{
		if(b+l==n-(n+1)/2)
			return(1);
		return(0);
	}
	else
	{
		ll x=min((n+1)/2-l,b);
		ll l1=l,b1=b;
		l+=x;
		b-=x;
		//cout<<l<<" "<<b<<" "<<r<<" "<<x<<"\n";
		if(l==(n+1)/2 && b+r==n-(n+1)/2)
			{
				ll val;
				if(n%2==1)
				{val=(nCr(b1,(n+1)/2-l1,mod)+nCr(b1,(n+1)/2-r,mod))%mod;
					//cout<<b1<<" "<<(n+1)/2-l1<<" "<<b1<<" "<<(n+1)/2-r<<"\n";
				}
				else
					{val=nCr(b1,(n+1)/2-l1,mod);
						//cout<<b1<<" "<<(n+1)/2-l1<<"\n";
					}
				return(val);

			}
		return(0);
	}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
//long long tt = clock();
#endif
ios_base::sync_with_stdio(NULL);  cin.tie(0); cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll p = 1000000007;
    InverseofNumber(p);
    InverseofFactorial(p);
    factorial(p);
int t;
cin>>t;
while(t--)
{    ll n,l,r,i,j;
cin>>n>>l>>r;
    ll ans=0;
    ll val=min(1-l,r-n);
    if(n%2==1)
    {	
    	ans+=(((nCr(n,(n+1)/2,mod)*2)%mod)*val)%mod;
    	ans%=mod;
    }
    else
    {
    	ans+=(((nCr(n,(n+1)/2,mod))%mod)*val)%mod;
    	ans%=mod;
    }
    //ans=0;
   // cout<<min(1-l,r-n)+1<<" "<<max(1-l,r-n);
   // exit(0);
for(i=min(1-l,r-n)+1;i<=max(1-l,r-n)+10;++i)
{ll left=0,right=0,both=0;
	/*for(j=1;j<=n;++j)
	{
		if(j-i>=l && j+i<=r)
		{
			both++;
		}
		else if(j-i>=l)
		{
			++left;
		}
		else if(j+i<=r)
		{
			++right;
		}
	}*/
	ll y=i+l,z=r-i;
	y=max(y,1ll);
	z=min(z,n);
	//cout<<y<<" "<<z<<" "<<n-z<<" "<<y-1<<" "<<z-y+1<<" "<<left<<" "<<right<<" "<<both<<"\n";
	left=n-z;
	right=y-1;
	both=z-y+1;

	ll x=pos(left,right,both,n);
	
	if(x!=0)
	{	ans+=x;
		ans%=mod;
		//cout<<i<<" "<<left<<" "<<right<<" "<<both<<" "<<x<<"\n";

	}
	else
		{//cout<<i<<"\n";
			break;
		}
}
cout<<ans<<"\n";
}
return(0);
}
////311322376

