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 <iostream>
using namespace std;

#define int long long

const int MAX_N = 2E5 + 100;
const int MOD = 1E9 + 7;

int bin(int x, int n) {
    int ret = 1;
    for (; n; n >>= 1, x = x * x % MOD)
        if (n & 1) ret = ret * x % MOD;
    return ret;
}

int fac[MAX_N], facInv[MAX_N];
void initInv(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % MOD;
    for (int i = 0; i <= n; ++i) facInv[i] = bin(fac[i], MOD - 2);
}

// 0 <= n <= m
inline int C(int n, int m) {
    return fac[m] * facInv[n] % MOD * facInv[m - n] % MOD;
}

int T;
int n, l, r;

signed main() {
    initInv(2E5);

    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n >> l >> r;
        int ans = 0;
        int ll = min(r - n, 1 - l);
        int rr = ll + (n + 1) / 2;

        if (n & 1) {
            ans += 2 * max(0ll, ll - 1) * C(n / 2, n) % MOD;
            for (int x = max(1ll, ll); x <= rr; ++x) {
                int rp = max(0ll, n - r + x);
                int lp = max(0ll, l + x - 1);
                if (lp <= n / 2 && rp <= n / 2 + 1) {
                    ans = (ans + C(n / 2 - lp, n - lp - rp)) % MOD;
                }
                if (lp <= n / 2 + 1 && rp <= n / 2) {
                    ans = (ans + C(n / 2 + 1 - lp, n - lp - rp)) % MOD;
                }
            }
        } else {
            ans += max(0ll, ll - 1) * C(n / 2, n) % MOD;
            for (int x = max(1ll, ll); x <= rr; ++x) {
                int rp = max(0ll, n - r + x);
                int lp = max(0ll, l + x - 1);
                if (lp <= n / 2 && rp <= n / 2) {
                    ans = (ans + C(n / 2 - lp, n - lp - rp)) % MOD;
                }
            }
        }

        cout << ans << '\n';
    }

    return 0;
}
