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>
#define int long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
using namespace std;
 
typedef double db;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
const int N=2e5+10,mod=1e9+7,inf=0x3f3f3f3f;
 
int read()
{
    int ret=0,f=1;char c=getchar();
    while(!isdigit(c)) {if(c=='-')f=0;c=getchar();}
    while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
    return f?ret:-ret;
}
 
struct Tnode
{
    int x,y;
    Tnode(int x=0,int y=0):x(x),y(y){}
};
 
void gmax(int &x,int y){x=max(x,y);}
int upm(int x){return x%mod;}
void up(int &x,int y){x=upm(x+y);}
int qpow(int x,int y)
{
    int ret=1;
    for(;y;y>>=1,x=1ll*x*x%mod)
        if(y&1) ret=1ll*ret*x%mod;
    return ret;
}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
 
int n,l,r;
int fac[N],inv[N],f[N];
 
int C(int n, int m) 
{
    if (!n) return 1;
    if (n<0 || m<0) return 0;
    return 1ll*fac[n]*f[n-m]%mod*f[m]%mod;
}
 
void init()
{
    fac[0]=fac[1]=inv[0]=inv[1]=f[0]=f[1]=1;
    for(int i=2;i<N;++i) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=qpow(i,mod-2),f[i]=1ll*f[i-1]*inv[i]%mod;
}
 
signed main() 
{
    init();
    for(int T=read();T--;)
    {
        n=read();l=read();r=read();
        int ans=C(n,n>>1)*min(r-n,1-l)%mod;
        if(n&1) up(ans,1ll*C(n,n>>1|1)*min(r-n,1-l)%mod);
        for(int x=min(r-n,1-l)+1; ; ++x) 
        {
            int ll=max(1ll,l+x),rr=min(n,r-x);
            if(ll-1>((n+1)>>1) || n-rr>((n+1)>>1)) break;
            int cnt=n/2-ll+1;
            int L=n-ll+1-(n-rr);
            if(L<0) break;
            if(!L) 
            {
                ans=ans+1;
                break;
            }
            up(ans,C(L,cnt));
            if(n&1) up(ans,C(L, cnt + 1));
        }
        printf("%lld\n",ans%mod);
    }
    return 0;
}