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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
const int maxn=200005,mod=1e9+7;
int t,n,L,R,cnt;
long long co[maxn],op[maxn];
ll qpow(ll b,ll k) {
    if (k==0) return 1;
    long long ans=1;
    while(k){
        if (k&1) ans=ans*b%mod;
        k>>=1,b=(b*b)%mod;
    }
    return ans;
}
void init(){
	co[0]=1,op[0]=1;
	for(int i=1;i<=200000;++i)
	{
		co[i]=(co[i-1]*i)%mod;
		op[i]=(op[i-1]*qpow(i,mod-2))%mod;
	}
}
struct node{
	int id,x,ty;
}p[maxn<<1];
bool cmp(node a,node b){
	return a.x<b.x;
}
bool fl[maxn][2];
int mi,ok,ad,bon;
void insert(int num)
{
	if(p[num].ty==0){
		fl[p[num].id][0]=1;
		if(fl[p[num].id][1]) ++ok,--ad;
		else ++mi;
	}else{//R
		fl[p[num].id][1]=1;
		if(fl[p[num].id][0]) ++ok,--mi;
		else ++ad;
	}
}
void In(int &now){
	while(p[now].x==p[now-1].x)
		insert(now),--now;
	insert(now);
}
long long C(int a,int b){
	return ((co[a]*op[a-b])%mod)*op[b]%mod;
}
long long cal(int l,int r){
	long long len=r-l+1,ans=0;
	if(n&1){
		if(mi+ok>=n/2+1) ans+=C(ok,n/2+1-mi);
		if(ad+ok>=n/2+1) ans+=C(ok,n/2-mi);
   	}else ans+=C(ok,n/2-mi);
	ans%=mod;
	return (ans*len)%mod;
}
int main(){
	init();
	scanf("%d",&t);
	while(t--)
	{
		cnt=0;
		memset(fl,0,sizeof(fl));
		mi=0,ad=0,ok=0;
		scanf("%d%d%d",&n,&L,&R);
		long long ans=0;
		for(int i=1;i<=n;++i)
		{
			int l=i-L,r=R-i;
			if(l!=0)p[++cnt].id=i,p[cnt].x=l,p[cnt].ty=0;
			if(r!=0)p[++cnt].id=i,p[cnt].x=r,p[cnt].ty=1;
		}
		p[++cnt].id=0,p[cnt].x=0,p[cnt].ty=2;
		sort(p+1,p+1+cnt,cmp);
		int now=cnt;
		while(now>1){
			In(now);
			if(mi+ad+ok==n&&mi+ok>=n/2&&ad+ok>=n/2){
				int l=p[now-1].x+1,r=p[now].x;
				ans=(ans+cal(l,r))%mod;
			}
			--now;
		}
		printf("%lld\n",(ans+mod)%mod);
	}
	return 0;
}