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 int N=2e5+10,mod=1e9+7;
int t,n,l,r;
ll Finv[N],fac[N],inv[N];
ll modpow(ll x,ll n,ll mod){
	ll res=1;
	for(;n;x=x*x%mod,n/=2)
	if(n&1)res=res*x%mod;
	return res;
}
void init(int n){
    inv[1]=1;
    for(int i=2;i<=n;++i)inv[i]=((mod-mod/i)*inv[mod%i])%mod;
	fac[0]=Finv[0]=1;
	for(int i=1;i<=n;++i)fac[i]=fac[i-1]*i%mod,Finv[i]=Finv[i-1]*inv[i]%mod;
	//Finv[n]=modpow(fac[n],mod-2,mod);
	//for(int i=n-1;i>=1;--i)Finv[i]=Finv[i+1]*(i+1)%mod;
}
ll C(ll n,ll m){
	if(m<0||m>n)return 0;
	return fac[n]*Finv[n-m]%mod*Finv[m]%mod;
}
int main(){
    init(N-5);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&l,&r);
        int lb=l-1,ub=r-n;//[l-1,r-n] 去掉0 其中的对称区间是任意取的 
		int a=-lb,b=ub;
		if(a>b)swap(a,b);
        int ans=1ll*a*C(n,n/2)%mod;
        if(n&1)ans=(ans+1ll*a*C(n,n/2)%mod)%mod;
        //ai-i 前面只能为正 后面只能为负 考虑枚举这个值 确定固定的前缀和后缀 剩下的任意取 
        //非对称区间有一个缀有i的限制
		int sz=b-a;
        for(int i=1;i<=min(sz,n);++i){
			int v=n-i;
			ans=(ans+C(v,n/2-i))%mod;
            if(n&1)ans=(ans+C(v,n/2+1-i))%mod;
		} 
        //任意区间外有两个有限制 其中一个有i的限制 另一个有i-sz的限制 
        for(int i=sz+1;i<=n;++i){
            int oth=i-sz,v=n-i-oth;
            ans=(ans+C(v,n/2-i))%mod;
            if(n&1)ans=(ans+C(v,n/2+1-i))%mod;
        }
        printf("%d\n",ans);
    }
    return 0;
} 