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 INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
inline int sgn(int x){
    return (x < 0 ? -1: (x > 0 ? 1: 0));
}
template<typename T>
T gcd(T a, T b){
    return (!b) ? a: gcd(b, a % b);
}
int poww(int a, int b){
    int res = 1;
    while (b > 0){
        if (b & 1) res = 1ll * res * a % MOD;
        a = 1ll * a * a % MOD, b >>= 1;
    }
    return res;
}
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int ddx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, ddy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

/*--------------------------------------------------------------------*/
/*--------------------------------------------------------------------*/

int fac[MAXN], ifac[MAXN];
inline int C(int n, int m){
    if (m > n) return 0;
    return 1ll * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
void facinit(){
    int n = 200000;
    fac[0] = ifac[0] = 1;
    REP(i, 1, n){
        fac[i] = 1ll * fac[i - 1] * i % MOD;
    }
    ifac[n] = poww(fac[n], MOD - 2);
    REPR(i, n - 1, 1)
        ifac[i] = 1ll * ifac[i + 1] * (i + 1) % MOD;
}
int n, l, r;
void init(){
    n = read(), l = read(), r = read();
}
inline int sv3(int a, int t){
    if (l + t > 1){
        if (r - t < n){
            return C(r - t - (l + t) + 1, n - a - l - t + 1);
        } else {
            return C(n - l - t + 1, a);
        }
    } else {
        if (r - t < n){
            return C(r - t, n - a);
        } else {
            return C(n, a);
        }
    }
    return 0;
}
int sv2(int a){
    int lb = 2 - l, rb = r - n + 1;
    int lim = min(a + r - n, n - l + 1 - a);
    int st = min(lb, rb);
    if (st > lim){
        return 1ll * st * C(n, a) % MOD;
    }
    // [1, st)
    int res = 1ll * (st - 1) * C(n, a) % MOD;
    REP(t, st, lim){
        res = modadd(res, sv3(a, t));
    }
    return res;
}
void solve(){
    int ans = 0;
    if (n & 1) ans = modadd(sv2(n >> 1), sv2((n + 1) >> 1));
    else ans = sv2(n >> 1);
    printf("%d\n", ans);
}
int main(){
    int T = read();
    facinit();
    while (T--){
        init();
        solve();
    }
    return 0;
}