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 all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; FOR(_, l, r) DB1(A, _); cerr << '\n';}
#define sz(x) ((int) (x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;

typedef pair<int, int> ii;
typedef array<int, 3> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vl;
const int N = 2e5 + 2, mod = 1e9 + 7;
int T, n, L, R, gt[N], igt[N];
int C(int i, int j) 
{
    assert(i <= j && i >= 0);
    return gt[j] * 1LL * igt[i] % mod * igt[j - i] % mod;
}
int power(int x, int y)
{
    int res = 1;
    while (y)
    {
        if (y & 1) res = res * 1LL * x % mod;
        x = x * 1LL * x % mod;
        y >>= 1;
    }
    return res;
}
bool in(int x, int l, int r) {return l <= x && x <= r;}
map<int, bool> done;
int main()
{
#ifdef HynDuf
    freopen("inp.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
    cin >> T;
    gt[0] = 1;
    FOR(i, 1, N - 2) gt[i] = gt[i - 1] * 1LL * i % mod;
    igt[N - 2] = power(gt[N - 2], mod - 2);
    FORD(i, N - 3, 0) igt[i] = igt[i + 1] * 1LL * (i + 1) % mod;
    while (T--)
    {
        cin >> n >> L >> R;
        int l = 1, r = R - 1, ans = 0;
        while (l <= r)
        {
            int m = (l + r) >> 1;
            if (m <= R - n && -m >= L - 1) l = m + 1;
            else r = m - 1;
        }
        ans = ((n % 2 == 1) ? 2 : 1) * C(n / 2, n) * 1LL * r % mod;
        done.clear();
        FORD(x, R - 1, R - n) if (x > r && done[x] == 0)
        {
            done[x] = 1;
            int cur = in(x, L - 1, R - 1) + in(-x, L - 1, R - 1);
            int am = 0, du = 0, both = 0;
            int touchRight = R - x, touchLeft = L - 1 + x;
            if (touchLeft > touchRight) continue;
            if (touchLeft <= 0) 
            {
                assert(cur == 2 && touchRight <= n - 1);
                both = touchRight;
                am = n - both;
            } else if (touchRight == touchLeft)
            {
                du = touchRight;
                am = n - du;
            } else 
            {
                assert(cur == 1);
                du = touchLeft;
                both = touchRight - touchLeft;
                am = n - du - both;
            }
            int ndu = n / 2 - du, nam = (n - n / 2) - am;
            if (ndu >= 0 && nam >= 0) (ans += C(ndu, both)) %= mod;
            if (n & 1) 
            {
                ndu = (n / 2 + 1) - du, nam = (n / 2) - am;
                if (ndu >= 0 && nam >= 0) (ans += C(nam, both)) %= mod;
            }
        }
        FOR(y, L - n, min(-1, L - 1)) if (-y > r && -y <= R - 1 && done[-y] == 0)
        {
            int x = -y;
            done[x] = 1;
            int cur = in(x, L - 1, R - 1) + in(-x, L - 1, R - 1);
            int am = 0, du = 0, both = 0;
            int touchRight = R - x, touchLeft = L - 1 + x;
            if (touchLeft > touchRight) continue;
            if (touchRight >= n)
            {
                du = touchLeft;
                both = n - du;
            } else if (touchRight == touchLeft)
            {
                du = touchRight;
                am = n - du;
            } else 
            {
                du = touchLeft;
                both = touchRight - touchLeft;
                am = n - du - both;
            }
            int ndu = n / 2 - du, nam = (n - n / 2) - am;
            if (ndu >= 0 && nam >= 0) (ans += C(ndu, both)) %= mod;
            if (n & 1) 
            {
                ndu = (n / 2 + 1) - du, nam = (n / 2) - am;
                if (ndu >= 0 && nam >= 0) (ans += C(nam, both)) %= mod;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}