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;

const int MOD = 1e9 +7;
const int LM = 2e5 + 4;

int N;
int l,r;

ll fact[LM],ifact[LM];

ll modPow(ll a, int k){
    if(k==0) return 1;
    ll d = modPow(a,k/2);
    if(k&1) return d*d%MOD*a%MOD;
    return d*d%MOD;
}
ll modInv(ll a){return modPow(a,MOD-2);}
ll C(int n, int k){
    if(n<k || n<0 || k<0) return 0;
    return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD;
}

int main(){
    fact[0] = ifact[0] = 1;
    for(int i=1;i<=2e5;i++){
        fact[i] = fact[i-1] * i % MOD;
        ifact[i] = ifact[i-1] * modInv(i) % MOD;
    }
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d", &N,&l,&r);
        ll ans = 0;
        ll cnt = min(1-l, r-N);
        // N/2개의 +a, N/2개의 -a로 구성
        if(N&1) ans += 2*cnt * C(N, N/2) % MOD;
        else ans += cnt * C(N, N/2) % MOD;
        int i = 1, j = N;
        ll a,b,c,d;
        a = N/2, b = (N+1)/2, c = (N+1)/2, d = N/2;
        while(1){
            cnt++;
            while(cnt > i-l) i++,a--,c--;
            while(cnt > r-j) j--,b--,d--;
            if(i-1>=j+1) break;
            ans += C(a+b,b);
            if(N&1) ans += C(c+d,d);
            ans %= MOD;
        }
        printf("%lld\n", ans%MOD);
    }
    return 0;
}
