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]. 
/**
 * Prof.Nicola
 * Way bellow my level
**/
#include <bits/stdc++.h>

using namespace std;
#define endl "\n"
#define mp make_pair
#define F first
#define S second
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
const long dx[4]={1,0,-1,0},dz[4]={0,1,0,-1};
const long double pi=3.14159265359;
const long long mod=1e9+7;
long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
template<class T>void re(T&x){cin>>x;}
template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);}
template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void out(T x){cout<<x<<" ";}
template<class T1,class T2>void out(pair<T1,T2>x){out(x.first);out(x.second);cout<<endl;}
template<class T>void out(vector<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(deque<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>T cross(complex<T>x,complex<T>z){return (conj(x)*z).imag();}
template<class T>T dot(complex<T>x,complex<T>z){return (conj(x)*z).real();}
long long power(long long x,long long p)
{
    if(p==0){
        return 1;
    }
    if(p%2==1){
        return (x*power(x,p-1))%mod;
    }
    long long z=power(x,p/2);
    z*=z;
    z%=mod;
    return z;
}
vector<long long>fact,inv;
void inverse(long x)
{
    fact.clear();
    inv.clear();
    fact.resize(x+1);
    inv.resize(x+1);
    fact[0]=1;
    for(long long i=1;i<=x;i++){
        fact[i]=(fact[i-1]*i)%mod;
    }
    inv[x]=power(fact[x],mod-2);
    for(long long i=x-1;i>=0;i--){
        inv[i]=(inv[i+1]*(i+1))%mod;
    }
}
long long nck(long long n,long long k)
{
    if(n<0||k<0||n<k){
        return 0;
    }
    long long z=(fact[n]*inv[k])%mod;
    z=(z*inv[n-k])%mod;
    return z;
}
int main()
{
    inverse(2e5);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long t,n,l,r,x,ans,a,b;
    cin>>t;
    REP(i,0,t){
        cin>>n>>l>>r;
        x=min(1-l,r-n);
        x=max(0ll,x);
        ans=(x*nck(n,n/2))%mod;
        if(n%2==1){
            ans*=2;
            ans%=mod;
        }
        x++;
        REP(j,0,n){
            a=max(0ll,n+x+j-r);
            b=max(0ll,l-(1-(x+j)));
            if(n%2==0){
                ans+=nck(n-a-b,abs(a-b)+max(0ll,((n-a-b-abs(a-b))/2)));
                ans%=mod;
                continue;
            }
            if(a==b){
                ans+=(2*nck(n-(2*a),(n-(2*a))/2));
                ans%=mod;
                continue;
            }
            ans+=nck(n-a-b,abs(a-b)-1+max(0ll,((n-a-b-abs(a-b)+1)/2)));
            ans%=mod;
            ans+=nck(n-a-b,abs(a-b)+max(0ll,((n-a-b-abs(a-b)+1)/2)));
            ans%=mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}
