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 ld long double
const int mod = 1e9 + 7;
ll binpow(ll a, ll b)
{
    if(!b)
        return 1;
    ll res = binpow(a, b / 2);
    res *= res, res %= mod;
    if(b % 2)
        res *= a, res %= mod;
    return res;
}
ll del(ll a, ll b)
{
    return (a*binpow(b, mod - 2))%mod;
}
ll cnk(ll n, ll k, vector<ll> &factorial)
{
    if(k < 0 || k > n)
        return 0;
    return del(factorial[n], (factorial[n - k] * factorial[k])%mod);
}
void solve()
{
    int n, l, r;
    cin>>n>>l>>r;
    vector<ll> factorial(n + 1);
    factorial[0] = 1;
    for(int i = 1; i <= n; i++)
        factorial[i] = factorial[i - 1]*i, factorial[i] %= mod;
    map<int, bool> used;
    ll ans = 0;
    for(int razn = min(-l + 1, r - n) + 1; razn <= min(-l + 1, r - n) + 1 + n; razn++)
    {
        if(razn <= 0)
            continue;
        int lborder = max(1, l + razn), rborder = min(r - razn, n);
        int cnt0 = lborder - 1, cnt1 = n - rborder, cnt01 = n - cnt0 - cnt1;
       // cout<<cnt0<<" "<<cnt1<<" "<<cnt01<<" "<<ans<<endl;
        if(cnt01 < 0)
            continue;
        if(n % 2 == 0)
            ans += cnk(cnt01, n / 2 - cnt0, factorial);
        else
            ans += cnk(cnt01, n / 2 - cnt0, factorial), ans += cnk(cnt01, n / 2 + 1 - cnt0, factorial);
        ans %= mod;
    }
    if(min(-l + 1, r - n) + 1 > 1)
    {
        if(n % 2 == 0)
            ans += cnk(n, n / 2, factorial)*min(-l + 1, r - n);
        else
            ans += ((cnk(n, n / 2, factorial) + cnk(n, n / 2 + 1, factorial))%mod)*min(-l + 1, r - n);
    }
    cout<<ans % mod<<endl;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
        solve();
}