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;

#define watch(x) cerr << (#x) << ": " << (x) << endl

typedef long long LL;

template<unsigned _MOD_> struct modint {
    
    static const int MOD = _MOD_;
    int v;
 
    modint(int _v = 0) {
        v = _v % MOD;
        if(v < 0) v += MOD;
    }

    explicit operator int() const { return v; }
    
    static int mod_inv(int a) {
        int g = MOD, r = a, x = 0, y = 1;
 
        while (r != 0) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        }
 
        return x < 0 ? x + MOD : x;
    }
 
    modint& operator+=(const modint &other) { v += other.v; if (v >= MOD) v -= MOD; return *this; }
    modint& operator-=(const modint &other) { v -= other.v; if (v < 0) v += MOD; return *this; }
    modint& operator*=(const modint &other) { v = (int)(((uint64_t) v*other.v)%MOD); return *this; }
    modint& operator/=(const modint &other) { return *this *= other.inv(); }
    friend modint operator+(const modint &a, const modint &b) { return modint(a) += b; }
    friend modint operator-(const modint &a, const modint &b) { return modint(a) -= b; }
    friend modint operator*(const modint &a, const modint &b) { return modint(a) *= b; }
    friend modint operator/(const modint &a, const modint &b) { return modint(a) /= b; }
    modint& operator++() { v = v == MOD - 1 ? 0 : v + 1; return *this; } 
    modint& operator--() { v = v == 0 ? MOD - 1 : v - 1; return *this; }
    modint operator++(int32_t) { modint before = *this; ++*this; return before; }
    modint operator--(int32_t) { modint before = *this; --*this; return before; }
    modint operator-() const { return v == 0 ? 0 : MOD - v; }
    bool operator==(const modint &other) const { return v == other.v; }
    bool operator!=(const modint &other) const { return v != other.v; }
    modint inv() const { return mod_inv(v); }
 
    modint pow(int p) const {
        modint a = *this, result = 1;
 
        while (p > 0) {
            if (p & 1)
                result *= a;
 
            a *= a;
            p >>= 1;
        }
 
        return result;
    }
 
    friend ostream& operator<<(ostream &out, const modint &m) { return out << m.v; }
};
const int MOD = 1000000007;
using mint = modint<MOD>;

void solve() {
    int n, l, r; cin >> n >> l >> r;

    vector<mint> f;
    f.emplace_back(mint(1));
    int sz = 1;
    auto fac = [&](int i) -> mint {
        while(i >= sz) {
            mint nxt = f[sz-1]*sz;
            f.emplace_back(nxt);
            sz++;
        }
        return f[i];
    };
    auto choose = [&](int n, int k) -> mint {
        if(n < k || k < 0) return 0;
        return fac(n)/fac(k)/fac(n-k);
    };

    int hf = n/2;
    
    mint ans = 0;

    int both_all = min(1-l, r-n);
    ans += choose(n, hf)*both_all;
    if(n & 1) {
        ans += choose(n, hf+1)*both_all;
    }

    for(int k = both_all+1; ; ++k) {
        int tp = max(0, k-(1-l));
        int bt = max(0, k-(r-n));

        if(tp+bt > n) {
            break;
        }

        ans += choose(n-tp-bt, hf-tp);
        if(n & 1) {
            ans += choose(n-tp-bt, hf+1-tp);
        }
    }
    
    cout << ans << '\n';
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t; cin >> t;
    while(t--) {
        solve();
    }
    
    return 0;
}
