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;
using ll = long long;

const int N = 2e5+10;
const int mod = 1e9+7;
int f[N],inf[N];
int n,l,r;

int mul(int a,int b){
    return a*1ll*b%mod;
}

int binPow(int a,int k){
    int res = 1;
    while(k>0){
        if(k&1) res = mul(res,a);
        a = mul(a,a);
        k >>= 1;
    }
    return res;
}

int norm(int a){
    while(a>=mod) a-=mod;
    while(a<0) a+=mod;
    return a;
}

int C(int n,int k){
    if(k<0 || n<k) return 0;
    return mul(f[n],mul(inf[n-k],inf[k]));
}

void precalc(){
    f[0] = inf[0] = 1;
    for(int i=1;i<N;++i){
        f[i] = mul(f[i-1],i);
        inf[i] = binPow(f[i],mod-2);
    }
}

void solve(){
    cin>>n>>l>>r;
    int t = min(1-l,r-n);
    int half = n/2;
    int ans = C(n,half);
    if(n&1){
        ans = norm(ans+C(n,half+1));
    }
    ans = mul(ans,t);
    for(int k=t+1;;k++){
        int lf = max(1,l+k);
        int rg = min(n,r-k);
        if(rg+1-lf<0) break;
        ans = norm(ans+C(rg-lf+1,half-(lf-1)));
        if(n&1) ans = norm(ans+C(rg-lf+1,half+1-(lf-1)));
    }
    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    precalc();
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }

    return 0;
}