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 endl '\n'
#define int long long //instead of int main, use signed main
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlll;
//const int INF = 100000000;
const int INF = 4500000000000000000;
typedef pair<int, char> pic;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int MOD = 1e9 + 7;

long long modpow(long long a, long long b) {
    long long ans = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            ans *= a;
            ans %= MOD;
        }
        a *= a;
        a %= MOD;
        b /= 2;
    }
    return ans;
}
long long modinv(long long a) {
    return modpow(a, MOD - 2);
}
int factsize = 1;
vector<long long> mf = { 1 };
vector<long long> mfi = { 1 };
long long modfact(int n) {
    if (factsize > n) {
        return mf[n];
    }
    else {
        for (int i = factsize; i <= n; i++) {
            factsize++;
            long long next = mf.back() * i % MOD;
            mf.push_back(next);
            mfi.push_back(modinv(next));
        }
        return mf[n];
    }
}
long long modfactinv(int n) {
    if (factsize > n) {
        return mfi[n];
    }
    else {
        return modinv(modfact(n));
    }
}
long long modbinom(int n, int k) {
    if (n < 0 || k < 0 || k > n) {
        return 0;
    }
    else {
        return modfact(n) * modfactinv(k) % MOD * modfactinv(n - k) % MOD;
    }
}

signed main(void) {
    IOS;

    int t; cin >> t;
    while (t--) {
        int n, l, r; cin >> n >> l >> r;
        int ans = 0;
        int k = min(1 - l, r - n);
        ans = k * modbinom(n, n / 2) * (n % 2 + 1) % MOD;
        for (k++; ; k++) {
            int left = max(1ll, l + k);
            int right = min(n, r - k);
            if (right + 1 < left) break;
            ans += modbinom(right + 1 - left, n / 2 - left + 1);
            if (n % 2) ans += modbinom(right + 1 - left, n / 2 + 2 - left);
            ans %= MOD;
        }
        cout << ans << endl;
    }
}

