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

#define ll long long
#define ar array
#define pi pair<int, int>
#define vi vector<int>
#define fi first;
#define se second;

void puti(int i) {
    printf("%d\n", i);
}

void printi(int i) {
    printf("%d ", i);
}

void scani(int *p) {
    scanf("%d", p);
}

void scans(char *p) {
    scanf("%s", p);
}

const int maxn = 2e5+5, mod = 1e9+7;
int t, n, l, r;
ll fact[maxn], inv[maxn];

ll modpow(ll a, ll b) {
    ll res = 1;
    for(; b>0; a=a*a%mod, b>>=1) if(b&1) res*=a,res%=mod;
    return res;
}

ll ncr(ll n, ll r) {
    return fact[n] * inv[r] % mod * inv[n-r] % mod;
}

ll ct(int d, int fl, int fr) {
    ll res = 0;
    if(l+d>1)fl--;
    if(r-d<n)fr--;
    while(fl>=0&&fr>=0) {
        res+=ncr(fl+fr, fl), res%=mod;
        d++;
        if(l+d>1)fl--;
        if(r-d<n)fr--;
    }
    return res;
}

void solve() {
    scani(&n), scani(&l), scani(&r);
    int d = min(1-l, r-n);
    ll res;
    if(n % 2) {
        res = 2 * ncr(n, n/2) % mod * d++ % mod;
        res += ct(d, n/2+1, n/2), res %= mod;
        res += ct(d, n/2, n/2+1), res %= mod;
    }
    else {
        res = ncr(n, n/2) * d++ % mod;
        res += ct(d, n/2, n/2), res %= mod;
    }
    puti(res);
}

int main() {
    fact[0]=inv[0]=1;
    for(int i = 1; i < maxn; i++) {
        fact[i]=fact[i-1]*i%mod;
        inv[i]=modpow(fact[i], mod-2);
    }
    scani(&t);
    for(int i = 0; i < t; i++) solve();
}