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 M 200005
typedef long long LL;
template<class T>void Rd(T &x){
	static char c;
	while(c=getchar(),!isdigit(c));
	for(x=0;isdigit(c);c=getchar())
		x=(x<<1)+(x<<3)+(c^48);
} 
template<class T>void Ps(T x){
	if(x==0)return;
	Ps(x/10);putchar(x%10^48);
} 
template<class T>void Printf(T x){
	if(x==0)putchar(48);
	else Ps(x);
	putchar('\n');
} 
template<class T>bool tomax(T &x,T y){
	if(x<y)return x=y,1;
	return 0;
}
template<class T>bool tomin(T &x,T y){
	if(x>y)return x=y,1;
	return 0;
}
bool MM1;
int n,l,r;
const int P=1e9+7;
#define calc(x,y) x=((y)+x)%P
void Mul(int &x,int y){
	x=1LL*x*y%P;
}
int fec[M],inv[M];
int qikpow(int a,int b){
	int ret=1;
	for(;b;b>>=1,Mul(a,a))
		if(b&1)Mul(ret,a);
	return ret;
}
void Init(){
	fec[0]=fec[1]=inv[0]=inv[1]=1;
	for(int i=2;i<M;i++)fec[i]=1LL*i*fec[i-1]%P,inv[i]=qikpow(fec[i],P-2);
}
int C(int a,int b){
	if(a>b)return 0;
	return 1LL*fec[b]*inv[a]%P*inv[b-a]%P;
}
bool MM2;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	printf("%lf\n",(&MM2-&MM1)/1024.0/1024.0);
	Init();
	int Cas;cin>>Cas; 
	while(Cas--){
		scanf("%d%d%d",&n,&l,&r);
		int x=min(1-l,r-n);
		int ans=1LL*x*C(n>>1,n)*((n&1)+1)%P;
		for(int i=x+1;;i++){
			int L=max(1,l+i),R=min(r-i,n);
			if(R+1<L||min(R,n-L+1)<(n>>1))break;
			int t=R-L+1;
			if(n+1&1)calc(ans,C((n>>1)-(L-1),t));
			else{
				calc(ans,C((n>>1)-(L-1),t));
				calc(ans,C((n>>1)-(L-1)+1,t));
			}
		}
		Printf(ans);
	}
	return 0;
} 