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]. 
//
#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
////
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#endif

#include <bits/stdc++.h>

#include <utility>

#define all(x) (x).begin(), (x).end()
#define allp(x) (x)->begin(), (x)->end()

#define pb push_back


using namespace std;
void dout() { cerr << endl; }
//typedef  long long ll;
typedef long double ld;
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

//using ll = long long;
//#ifdef __int128
//using hll = __int128;
//#endif
//using pii = pair<ll, ll>;
//using ld = long double;

template <typename T>
void do_uniq(vector<T> &vec){
    sort(all(vec));
    vec.resize(unique(all(vec)) - vec.begin());
}

#ifndef ONLINE_JUDGE

clock_t timestamp_start = clock();
void time_calc()
{
    cerr << (ld)(clock() - timestamp_start) / CLOCKS_PER_SEC << endl;
}
#endif


#ifdef _getchar_nolock
#else
#    define _getchar_nolock getchar_unlocked
#endif

#define integer int

integer mod = 1e9 + 7;

integer ml(integer a, integer b) {
    return (a * 1ll * b) % mod;
}

integer add(integer a, integer b) {
    return (a + b) % mod;
}

integer sub(integer a, integer b) {
    return add(a, mod - b);
}

integer sq(integer a) {
    return ml(a, a);
}

integer b_p(integer b, integer p) {
    if (p == 0) return 1;
    if (p & 1) return ml(b, b_p(b, p - 1));
    return sq(b_p(b, p >> 1));
}


#define solvsh
#define multi
#ifdef solvsh

const int MAXN = 5e5 + 321;

int dp[MAXN];


typedef long long ll;

ll f[MAXN];
ll bf[MAXN];

ll nCr(int n, int r){
    return ml(f[n], ml(bf[n - r], bf[r]));
}

void prec(){

    for (int i = 0; i < MAXN; ++ i) {
        f[i] = i == 0 ? 1 : ml(i, f[i - 1]);
    }

    bf[MAXN - 1] = b_p(f[MAXN - 1], mod - 2);


    for (int i = MAXN - 2; i >= 0; -- i) {
        bf[i] = ml(1 + i, bf[i + 1]);
    }

}


void solve() {


    ll n, l, r;
    cin >> n >> l >> r;

    ll diff = min(1 - l, r - n);

    int hlf = n / 2;

    ll answr = ml(diff, nCr(n, hlf));
    if (n % 2 == 1) {
        answr = ml(answr, 2);
    }

    int i1 = 1;
    int i2 = n;

    for (int curr = diff + 1; true; ++ curr) {

        while (i1 - curr < l) ++i1;
        while (i2 + curr > r) --i2;

        bool ok = false;

        int len = i2 - i1 + 1;
        int neg = hlf - (n - i2);

        if (neg >= 0 && neg <= len ) {

            ll aa = nCr(len, neg);
            ok = true;
            answr = add(answr, aa);
        }


        if (n % 2 == 1) {

            int neg = hlf - (n - i2) + 1 ;

            if (neg >= 0 && neg <= len) {
                ll aa = nCr(len, neg);
                ok = true;
                answr = add(answr, aa);
            }

        }

        if (!ok) break;
    }

    cout << answr << "\n";
}

#else

#endif


void multisolve() {

    prec();

    int t;

    cin >> t;

    int i = 1;
    while (t--) {
//        cout << "Case #" << i << ": ";
        solve();
//        i++;
    }
}

#ifndef ONLINE_JUDGE

void gen() {
#ifndef ONLINE_JUDGE
    freopen("../input.in", "w", stdout);
#endif

    int n = 1e5;
    cout << "1\n";
    cout << n << "\n";
    for (int i = 0; i< n; ++ i) cout << rand() % 10<< " ";
}


#endif

#define int int
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(5);
    cerr << fixed << setprecision(20);

#ifdef multi

#ifndef ONLINE_JUDGE
    freopen("../input.in", "r", stdin);
#endif
//    gen();
    multisolve();
//    checkk();
#else

    #ifndef ONLINE_JUDGE
    freopen("../input.in", "r", stdin);
#else
#endif
    solve();
#endif
//     time_calc();
}