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 LL long long
using namespace std;
const int maxn = 2e5 + 7;
const LL mod = 1e9 + 7;
LL n = 2e5 + 5, l, r;
LL Qmul(LL a, LL b, LL mod) {
    LL ans = 0;
    while (b) {
        if (b & 1) {
            b--;
            ans = (ans + a) % mod;
        }
        b /= 2;
        a = (a + a) % mod;
    }
    return ans % mod;
}
LL fac[maxn], inv[maxn];
LL pow(long long x, LL k) {
    long long ans = 1;
    while (k) {
        if (k & 1)
            ans = ans * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return ans;
}
void init() {
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % mod;
    inv[n] = pow(fac[n], mod - 2);
    for (int i = n - 1; i >= 1; i--)
        inv[i] = inv[i + 1] * (i + 1) % mod;
}
LL getC(int n, int m) {
    if (m > n || m < 0)
        return 0;
    else if (m == n)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    init();
    while (t--) {
        cin >> n >> l >> r;
        LL k = min(1 - l, r - n);
        LL fz = n / 2;
        LL ans = 0;
        ans = Qmul(k, getC(n, fz), mod);
        if (n % 2)
            ans = (ans + Qmul(k, getC(n, fz + 1), mod)) % mod;
        for (LL i = k + 1;; i++) {
            LL le = max(1LL, l + i);
            LL ri = min(n, r - i);
            LL tmp = ri - le + 1;
            if (tmp < 0)
                break;
            ans = (ans + getC(tmp, fz - le + 1)) % mod;
            if (n % 2)
                ans = (ans + getC(tmp, fz - le + 2)) % mod;
        }
        cout << ans << endl;
    }
}