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 <string.h>
#include <stdio.h>
#include <math.h>
#include <map>
#include <queue>
#include <vector>
#include <numeric>
#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

#define mp    make_pair
#define pb    push_back
#define F     first
#define S     second
#define ab(x) (((x)<0)?-(x):(x))

#define MOD 1000000007

class nCrModular {
public:
    ll mod;
    vector<ll> fac;

    nCrModular(int n, ll _mod) {
        mod = _mod;
        fac.resize(n + 1);

        fac[0] = 1;
        for (int i = 1; i <= n; i++)
            fac[i] = (fac[i - 1] * i) % mod;
    }

    ll pow(ll x, ll y) {
        ll r = 1;
        for (x = x % mod; y; y >>= 1, x = (x * x) % mod)
            if (y & 1) r = (r * x) % mod;
        return r;
    }

    ll inv(ll x) {
        return pow(x, mod - 2);
    }

    ll nCr(ll n, ll r) {
        if (n < r) return 0;
        if (r == 0) return 1;
        return ((fac[n] * inv(fac[r]) % mod) * inv(fac[n - r])) % mod;
    }
} ncr(200000, MOD);


void solve() {
    int n, s, e;
    cin >> n >> s >> e;

    int k = min(min(ab(s - 1), ab(e - 1)), min(ab(s - n), ab(e - n)));
    int L = 1, R = n, m1 = n / 2, m2 = (n + 1) / 2;
    ll r = 0;
    for (int i = 0; i <= m2 - m1; i++) {
        int need = m1 + i;
        r = (r + ncr.nCr(n, need) * k) % MOD;
    }

    for (k = k + 1;; k++) {
        if (!(s - L <= -k && k <= e - L)) L++;
        if (!(s - R <= -k && k <= e - R)) R--;
        if (R - L + 1 < 0) break;
        int plus = L - 1;
        int minus = n - R;
        if (plus > m2 || minus > m2) break;

        for (int i = 0; i <= m2 - m1; i++) {
            int need = m1 + i - plus;
            r = (r + ncr.nCr(R - L + 1, need)) % MOD;
        }
    }

    cout << r << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int test_case;
    cin >> test_case;
    while (test_case--)
        solve();
}
