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;
const LL MOD=1e9+7;
LL QuickPow(LL x,LL p)
{
	LL ans=1,base=x;
	while(p)
	{
		if(p&1)	ans=ans*base%MOD;
		base=base*base%MOD;
		p>>=1;
	}
	return ans;
}
LL l,r,fac[200005],ifac[200005];
LL C(LL n,LL m){if(n<m)	return 0;return fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;}
LL n;
int main(){
	fac[0]=1;
	for(LL i=1;i<=200000;++i)	fac[i]=i*fac[i-1]%MOD;
	ifac[200000]=QuickPow(fac[200000],MOD-2);
	for(LL i=199999;~i;--i)	ifac[i]=ifac[i+1]*(i+1)%MOD;
	LL T;
	scanf("%lld",&T);
	while(T-->0)
	{
		scanf("%lld %lld %lld",&n,&l,&r);
		LL ans=0,sp1=2e9,sp2=2e9;
		for(LL i=1;i<=n;++i)	sp1=min(sp1,max(i-l,r-i));
		for(LL i=1;i<=n;++i)	sp2=min(sp2,min(i-l,r-i));
		ans=sp2*C(n,n/2)%MOD;
		if(n&1)	ans+=sp2*C(n,n/2+1)%MOD;
		ans%=MOD;
		for(LL i=sp2+1;i<=sp1;++i)
		{
			LL st1=max(0ll,min(n,n-i-l+1)),st2=max(0ll,min(n,r-i)),st3=max(0ll,min({st1,st2,r-l-2*i+1}));
			LL dl1=st1-st3,dl2=st2-st3;
			if(max(dl1,dl2)>n/2+(n&1))	break;
			(ans+=C(n-dl1-dl2,n/2-dl1))%=MOD;
			if(n&1)	(ans+=C(n-dl1-dl2,n/2-dl2))%=MOD;
		}
		printf("%lld\n",ans);
	}
	return 0;
}