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" // Ignacy Boehlke
using namespace std;     // XIII LO Szczecin
template<class A, class B> ostream& operator << (ostream& os, const pair<A, B>& p) {return os << '{' << p.first << ", " << p.second << '}';}
template<class T> auto operator << (ostream& os, const T& v) -> decltype(v.begin(), os) {os << '{';for (auto i : v) os << i << ", ";return os << '}';}
#ifdef DEBUG
#define D(x...) x
#else
#define D(x...)
#endif
#define LN(x) D(cerr << #x << ": " << x << ' ';)
#define LOG(x) D(cerr << #x << ": " << x << '\n';)
#define ssize(x) ((int)x.size())
#define FOR(a, b, c) for(int a = (b); a <= (c); ++a)
#define REP(a, b) FOR(a, 0, b - 1)
#define ALL(x) (x).begin(), (x).end()
#define fi first
#define se second
typedef long long ll;

constexpr int MOD = 1000000007;

inline int mul(int a, int b) {
    return (int)(((ll)a * b) % MOD);
}

inline int add(int a, int b) {
    return (a + b >= MOD ? a + b - MOD : a + b);
}

int power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = mul(res, a);
        b >>= 1;
        a = mul(a, a);
    }
    return res;
}

int inv(int x) {
    return power(x, MOD - 2);
}

constexpr int MAX = 200000;
vector<int> fac(MAX + 1), ifac(MAX + 1);

void mkfac() {
    fac[0] = 1;
    FOR(i, 1, MAX) fac[i] = mul(fac[i - 1], i);
    ifac[MAX] = inv(fac[MAX]);
    for (int i = MAX - 1; i >= 0; --i) ifac[i] = mul(ifac[i + 1], i + 1);
}

int newton(int a, int b) {
    return mul(fac[a], mul(ifac[a - b], ifac[b]));
}

void solve() {
    int n, l, r;
    scanf("%d%d%d", &n, &l, &r);
    int x = min(r - n, 1 - l);
    LOG(x);
    int res = mul(x, mul(1 + (n & 1), newton(n, n / 2)));

    int a = n / 2, sz = n;
    for (++x;; ++x) {
        if (1 - x < l) --a, --sz;
        if (n + x > r) --sz;
        if (sz < a) break;
        if (a < 0) {
            if (n & 1 && sz > a) res = add(res, 1);
            break;
        }
        res = add(res, newton(sz, a));
        if ((n & 1) && sz > a) res = add(res, newton(sz, a + 1));
    }
    printf("%d\n", res);
}

int main() {
    mkfac();
    int T;
    scanf("%d", &T);
    while (T--) solve();
}

