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;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define FF first
#define SS second
#define pb push_back
#define sz(x) (int)x.size()
#define oo 1e9
#define eps 1e-9
#define PI acos(-1.0)
#define lb lower_bound
#define ub upper_bound
#define all(a) (a).begin(), (a).end()
#define log2i(x) (64 - __builtin_clzll(1ll*(x)) - 1)
#define INF 0x7f7f7f7f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<ii, ii> Li;
const int N = 2e5+7, M=100+7;
const int MOD = 1e9+7;
const int base=30;

int n, m, k, t;

int fac[N]{1}, invf[N]{1};

int add(int a, int b) {
    a+=b; if(a>MOD) a-=MOD;
    return a;
}
int mul(int a, int b) {return (1LL*a*b)%MOD;}
void gcd(int a, int b, int &x, int &y) {
    if(!b) {x=1, y=0; return;}
    int tx, ty; gcd(b, a%b, tx, ty);
    x=ty, y=tx-(a/b)*ty;
}
int inv(int a) {
    int x, y; gcd(a, MOD, x, y);
    return (x%MOD+MOD)%MOD;
}
int nCk(int n, int k) {
    if(n<k||k<0) return 0;
    return mul(fac[n], mul(invf[n-k], invf[k]));
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d", &t);
    for(int i=1;i<N;i++) {
        fac[i]=mul(fac[i-1], i);
        invf[i]=inv(fac[i]);
    }
    while(t--) {
        scanf("%d%d%d", &n, &m, &k);
        int r=min(1-m, k-n), ans=nCk(n, n/2);
        if(n&1) ans=mul(ans, 2); ans=mul(ans, r);
        for(int pos, neg, i=r+1; i<=r+n;i++) {
            pos=max(0, m+i-1), neg=max(0, n-k+i);
            int tmp=n-pos-neg;
            if(tmp<0) break;
            ans=add(ans, nCk(tmp, n/2-pos));
            if(n&1) ans=add(ans, nCk(tmp, n/2-neg));
        }
        printf("%d\n", ans);
    }
    return 0;
}
/* stuff you should look for
    - int overflow, array   bounds
    - special cases (n=1?)
    - do smth instead of do nothing and stay organized
    - WRITE STUFF DOWN
    - DONT JUST STICK ON ONE APPROACH
*/
