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 ls i<<1
#define rs i<<1|1
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef vector<int> vct;
typedef pair<int,int> pii;
const int N=2E5+1;
const int inf=1<<30;
ll read()
{
    ll a=0;
    char b=1,c;
    do if((c=getchar())==45)b=-1;while(c<48||c>57);
    do a=(a<<3)+(a<<1)+(c&15);while((c=getchar())>47&&c<58);
    return a*b;
}
void write(ll x,char c)
{
    if(x<0)putchar(45),x=-x;
    char a[20],s=0;
    do a[++s]=x%10|48;while(x/=10);
    do putchar(a[s]);while(--s);
    putchar(c);
}
const int p=1E9+7;
int n,l,r,a,b;
int fac[N],inv[N];
int solve(int u,int v)
{
    int res=0;
    for(int i=b,las=0;i>=a;--i)
    {
        int y=v-max(l+i-1,0),z=u-max(n-r+i,0),now=0;
        if(y>=0&&z>=0)now=(fac[y+z]*1LL*inv[y]%p*inv[z]%p);
        res=(res+(now-las+p)*1LL*i)%p;
        las=now;
    }
    return res;
}
int main()
{
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(int i=2;i<N;++i)inv[i]=(p-p/i)*1LL*inv[p%i]%p;
    for(int i=2;i<N;++i)
    {
        fac[i]=fac[i-1]*1LL*i%p;
        inv[i]=inv[i-1]*1LL*inv[i]%p;
    }
    for(int x=read();x--;)
    {
        n=read(),l=read(),r=read(),a=min(1-l,r-n),b=a+n-1;
        int m=n>>1;
        if(n&1)write((solve(m,n-m)+solve(n-m,m))%p,'\n');
        else write(solve(m,m),'\n');
    }
}
