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;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int ssq   =  460;
const ll  inf   =  2e18;

ll fact[maxn5];
int n, l, r, g1, g2, t1, t2;

ll pw(ll a, ll b){return b == 0 ? 1LL : (pw(a * a % mod, b / 2) * (b % 2 == 1 ? a : 1LL))%mod;}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    fact[0] = 1;
    for(int i = 1; i < maxn5; i++) fact[i] = (fact[i - 1] * i) % mod;
    int tt; cin >> tt;
    while(tt--){
        cin >> n >> l >> r;
        g1 = n / 2; g2 = n / 2 + n % 2;
        int lo = min(r - g1, g2 - l + 1);
        if(g2 != g1 && r - g1 == lo && g2 - l  + 1 == lo) lo--;
        t1 = n - min(n, (r - lo));
        t2 = max(0, l + lo - 1);
        ll ans = 0;
        if(t1 > t2) swap(t1, t2);
        while(lo > 0 && t2 > 0){
            ans += (fact[n - t2 - t1] * pw(fact[g2 - t2] * fact[n - t2 - t1 - (g2 - t2)] % mod, mod - 2)) % mod;
            if(t2 <= g1 && g1 != g2) 
                ans += (fact[n - t2 - t1] * pw(fact[g1 - t2] * fact[n - t2 - t1 - (g1 - t2)] % mod, mod - 2)) % mod;
            ans %= mod;
            t1--; t2--; lo--;
            t1 = max(t1, 0);
            t2 = max(t2, 0);
        }
        ans += (lo * (g1 != g2 ? 2 : 1) % mod) * ((fact[n] * pw(fact[g1] * fact[g2] % mod, mod - 2))%mod) % mod;
        cout << ans % mod << endll;
    }
}