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 fast            ios_base::sync_with_stdio(false); cin.tie(NULL);
#define lli             long long int
#define ld              long double
#define pll             pair<lli,lli>
#define ve              vector<lli>
#define vep             vector<pll>
#define pb              push_back
#define mp              make_pair
#define all(x)          (x).begin(),(x).end()
#define fr(i,a,n)       for(lli i=a;i<(n);i++)
#define frx(i,a,n)      for(lli i=a;i>(n);i--)
#define lb              lower_bound
#define ub              upper_bound
#define F               first
#define S               second
#define endl            '\n'
#define op(x)           cout<<x<<endl
#define op2(x,y)        cout<<x<<" "<<y<<endl
#define parr(arr,a,n)   fr(u,a,n) cout<<arr[u]<<" "; cout<<endl
#define yes             cout<<"YES"<<endl
#define no              cout<<"NO"<<endl
#define mem(a,x)        memset(a,x,sizeof(a))
#define sz(a) 		    ((lli) a.size())
#define INF             (lli)1e18

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}

//-----------------------------------------CODE_BEGINS----------------------------//
const lli N=2e5+10;
lli mod=1e9+7;
lli fac[N];
void precomp(lli p=mod){
    fac[0] = 1; 
    fr(i,1,N) fac[i] = fac[i-1]*i%p; 
}

lli power(lli x, lli y, lli p=mod){ 
    lli res = 1;      
    x = x % p;   
    while (y > 0){ 
        if (y & 1) res = (res*x) % p; 
        y = y>>1; 
        x = (x*x) % p; 
    } 
    return res; 
} 
  
lli modinv(lli n, lli p=mod) { 
    return power(n, p-2, p); 
}

lli ncr(lli n, lli r, lli p=mod) 
{ 
    if (r<0 || r>n) return 0;
    if (r==0) return 1;
    return (fac[n]* modinv(fac[r], p) % p * modinv(fac[n-r], p) % p) % p; 
}

void solve(){
    lli n,l,r,ans=0;
    cin>>n>>l>>r;
    if(r-n>-(l-1)){
        lli rr=1-(l-n),ll=1-(r-n);
        l=ll,r=rr;
    }
    ///from  1 to r-n-1
    lli tmp=(ncr(n,(n+1)/2)*max(0LL,r-n-1))%mod;
    ans=(ans+tmp)%mod;
    if(n%2) ans=(ans+tmp)%mod;
    ///from r-n to r-1
    fr(i,max(1LL,r-n),r){
        lli tmp1=min(n,r-i),tmp2=min(n,-i-(l-n)+1);
        if(tmp1+tmp2<n)break;
        lli pp=min(n-tmp2,tmp1),nn=min(n-tmp1,tmp2),dd=n-pp-nn;
        lli xx=max(n/2-pp,0LL),yy=max((n+1)/2-pp,0LL);
        ans=(ans+ncr(dd,xx))%mod;
        if(n%2) ans=(ans+ncr(dd,yy))%mod;
    }
    op(ans);
}

int main(){
    fast;
    precomp();
    lli test=1;
    cin>>test;
    while(test--){
        solve();
    }
}