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>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define int long long
#define ick cout<<"ickbmi32.9\n"
using namespace std;
int n, arr[1000005];    
int MOD = 1000000007;
vector<int> conn[1000005];
bool vi[1000005];
void init(int k) {
    for(int i = 0; i <= k; i++) {
        arr[i] = 0;
        vi[i] = false;
        conn[i].clear();
    }
}
bool isprime(int k) {
    for(int i = 2; i <= sqrt(k); i++) if(k % i == 0) return false; 
    return true;
}
int bm(int a, int b, int mod) {
    if(b == 0) return 1; 
    int t = bm(a, b / 2, mod); 
    t = t * t % mod; 
    return (b % 2 == 1 ? t * a % mod : t);
}
int fac[200005];
int inv(int a, int mod) {return bm(a, mod - 2, mod);}
int ncr(int a, int b) {
    return fac[a] * inv(fac[b], MOD) % MOD * inv(fac[a - b], MOD) % MOD;
}
void solve() {  
    int l, r;
    cin >> n >> l >> r;
    l *= -1; l++;
    r -= n; 
    int ans = 0;
    int c1 = n / 2;
    int c2 = n - c1;
    int t = min(l, r);
    l -= t;
    r -= t;
    for(int i = 0; i <= n + 5; i++) {
        int ll, rr;
        ll = rr = 0;
        ll = max(ll, i - l);
        rr = max(rr, i - r);
        if(ll + rr > n) break;
        int tans = 0;
        if(!(ll > c1 || n - ll - rr < c1 - ll)) tans += ncr(n - ll - rr, c1 - ll);
        if(n % 2 != 0) {
            if(!(ll > c2 || n - ll - rr < c2 - ll)) tans += ncr(n - ll - rr, c2 - ll);  
        }
        //cout << i << tans << '\n';
        if(i == 0) ans = (ans + tans * t) % MOD;
        else ans = (ans + tans) % MOD;
    }
    cout << ans << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    fac[0] = 1;
    for(int i = 1; i <= 200000; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    int t = 1;  
    cin >> t; // REMOVE THIS LINE IF ONLY 1 CASE
    while(t--) solve();
    return 0;
}