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;
using ll = long long;
using ld = long double;
const int mxn = 2e5+10;
const int mod = 1e9+7;

ll fact[mxn], inv_fact[mxn], inv[mxn];

void pre() {
    fact[0] = 1;
    for(int i=1; i<mxn; i++) {
        fact[i] = fact[i-1]*i%mod;
    }
    inv[0] = inv[1] = 1;
    for(int i=2; i<mxn; i++) {
        inv[i] = (mod - mod/i) * inv[mod%i] % mod;
    }
    inv_fact[0] = 1;
    for(int i=1; i<mxn; i++) {
        inv_fact[i] = inv_fact[i-1] * inv[i] % mod;
    }
}

ll binom(int n, int k) {
    if(k>n or k<0 or n<0) return 0;
    return fact[n] * inv_fact[k] %mod * inv_fact[n-k] %mod;
}

int n, l, r;

ll count(int sizeMX, int sizeMN) {
    ll ret = min(r - sizeMX, sizeMX+1 - l);
    for(int j = sizeMX+1; j<=n; j++) {
        int d = r - j;
        int i = l + d;
        if(i<1) i = 1;
        if(!(i>=1 and i<j)) continue;
        ret += d * binom(j - i, j - sizeMX) %mod; ret %=mod;
    }

    for(int i = sizeMX; i>=1; i--) {
        int d = i - l;
        int j = r - d - 1;
        if(j>n) j = n;
        if(!(j>i and j<=n)) continue;
        ret += d * binom(j - i, sizeMX - i + 1) %mod; ret %=mod;
    }
    return ret%mod;
}

void solve() {
    ll ret = 0;
    ret = count((n+1)/2, n - (n+1)/2);
    if(n&1) ret += count(n - (n+1)/2, (n+1)/2);
    ret %= mod;
    cout << ret << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    pre();

    int tc; cin>>tc;
    while(tc--) {
        cin>>n;
        cin>>l>>r;
        solve();
    }

    return 0;
}