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;
 
/* 
find my code templates at https://github.com/galencolin/cp-templates
also maybe subscribe please thanks 
*/
 
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL);} 
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
#define rep(i,x,n) for(long long i = x; i < n; i++) 
#define rev(i,x,n) for(long long i = n-1; i >= x; --i)
#define ff            first
#define ss            second 
#define int long long 
#define pb push_back
#define all(x)  (x).begin() , (x).end()
#define pii pair<long long ,long long > 

typedef long long ll;
// typedef int ll;
// #pragma warning("int")
 
typedef long double lld;
typedef unsigned long long ull;
 
 
mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rng(61378913);
/* usage - just do rng() */
 
void usaco(string filename) {
  // #pragma message("be careful, freopen may be wrong")
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}
 
// #include <atcoder/all>
// using namespace atcoder;
 
const ll N = 2e5+7;
   const ll mod = 1000000007;
   const ll mod1 = 998244353;
// ll mod1;


 
ll n, m, q, k, l, r, x, y, z;
const ll template_array_size = 1e6 + 16614;
//ll a[template_array_size];
//ll b[template_array_size];
//ll c[template_array_size]; 

 
inline void add(ll& a, ll b) {
    a += b;
    if (a >= mod1) a -= mod1;
}
int mul(int a, int b) {
    return a * 1ll * b % mod1;
} 


int binpow(int a,int p=mod-2){
    int result = 1;
    while (p > 0) {
        if (p & 1)
            result = a * result % mod;
        a = a * a % mod;
        p >>= 1;
    }
    return result;
}
int fact[N],invfact[N];
void init(){
    int p=mod;
    fact[0]=1;
    int i;
    for(i=1;i<N;i++){
        fact[i]=i*fact[i-1]%p;
    }
    i--;
    invfact[i]=binpow(fact[i],p-2);//fermat theorem
    for(i--;i>=0;i--){
        invfact[i]=invfact[i+1]*(i+1)%p;
    }
}
int ncr(int n,int r){int p=mod;
    if(r > n || n < 0 || r < 0)return 0;
    return fact[n]*invfact[r]%p*invfact[n-r]%p;
}


void solve(int tc = 0) {  
cin >> n >> l >> r;
x = min((r - n), -(l - 1));//(x,-x) pairs
int ans = x*ncr(n,n/2) % mod;
if(n % 2){
    ans += x*ncr(n,n - n/2) % mod;//n/2,n/2+1 indices of +x
    ans %= mod;} 
rep(i,0,n){
    k = x + i + 1;
        int p = min(n, r - k);
        int m = min(n, n + 1 - (l + k));
        if(p < 0 || m < 0) break;
        int b = n - ((n - p) + (n - m));
        p -= b;
        m -= b;
        
        if(n % 2){
            int u = n / 2;
            ans = (ans + ncr(b, u - p)) % mod;
            ans = (ans + ncr(b, u - m)) % mod;
        }
        else{
            int u = n / 2;
            ans = (ans + ncr(b, u - p)) % mod;
        }
        
    }
cout <<ans<<endl;

}

signed main() {
    #ifdef galen_colin_local
        auto begin = std::chrono::high_resolution_clock::now();
    #endif
    
    send help
 
    #ifndef galen_colin_local
        // usaco("code");
    #endif
    
    // usaco("cowland");
    
    // freopen("tc.cpp", "r", stdin);
    // freopen("tc2.cpp", "w", stdout);
        
    cout << setprecision(15) << fixed;
    init();
        
    int tc = 1;
    cin >> tc;   
    for (int t = 0; t < tc; t++) solve(t);
    
    #ifdef galen_colin_local
        auto end = std::chrono::high_resolution_clock::now();
        cerr << setprecision(4) << fixed;
        cerr << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
    #endif
}