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;
const int64_t MOD = 1e9 + 7;
const int N = 2e5 + 5;

int64_t mpow(int64_t b,int64_t e,int64_t m){
    int64_t r = 1;
    while(e > 0){
        if(e & 1){
            r = (r*b)%m;
        }
        b = (b*b)%m;
        e >>= 1;
    }
    return r;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int64_t fact[N],ifact[N];
    ifact[0] = fact[0] = 1;
    for(int i=1;i<N;i++){
        fact[i] = (i * fact[i-1]) % MOD;
        ifact[i] = mpow(fact[i],MOD-2,MOD);
    }
    auto comb = [&](int x,int y){ // xCy
        return (fact[x]*ifact[x-y]%MOD*ifact[y])%MOD;
    };
    int t;
    cin >> t;
    while(t--){
        int n,l,r;
        cin >> n >> l >> r;
        int x = min(1-l,r-n);
        int L=0,R=n+1;
        int64_t res = (x*(((n%2)+1)*comb(n,n/2))%MOD)%MOD;
        res %= MOD;
        for(int i=x+1;;i++){
            while(L+1-i < l) L++;
            while(R-1+i > r) R--;
            if(L > (n+1)/2 || n+1-R > (n+1)/2 || R-L-1 < 0) break;
            if(n%2 == 1){
                if(L <= n/2) res = (res+comb(R-L-1,n/2-L))%MOD;
                if(L <= (n+1)/2) res = (res+comb(R-L-1,(n+1)/2-L))%MOD;
            }else{
                res = (res+comb(R-L-1,n/2-L))%MOD;
            }
        }
        cout << (res%MOD+MOD)%MOD << "\n";
    }
}