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 <iostream>
#include <bits/stdc++.h>    // Standard Template Library
#include <cmath>
#include <climits>    // for range values of variable types
#include <algorithm>


#define ll long long
#define F(a,b,i) for(int i=a;i<b;i++)
#define FN(a,b,i) for(int i=a;i>=b;i--)


using namespace std;


const int M = 1e9+7;


int gcd(int a,int b){
    while(b>0){
        int p=a%b;
        a=b;
        b=p;
    }
    return a;
}


ll bexp(ll a, int b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}


ll bexpM(ll a, int b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%M;
        a = (a * a)%M;
        b >>= 1;
    }
    return res;
}


ll nCk(int n,int k){    // incorrect as of now
    ll res=1;
    F(k+1,n+1,i)
        res=res*i;
    ll p=1;
    F(2,n-k+1,i)
        p=p*i;
    res=res/p;
    return res;
}
ll mymod(ll a,ll b)
{
	return (((a = a%b) < 0) ? a + b : a);
}
ll gcdExtended(ll a, ll b, ll *x, ll *y) 
{ 
		if (a == 0) 
		{ 
				*x = 0, *y = 1; 
				return b; 
		} 
		ll x1, y1; 
		ll gcd = gcdExtended(b%a, a, &x1, &y1);
		*x = y1 - (b/a) * x1; 
		*y = x1; 
		return gcd; 
}
ll modInverse(ll a, ll m) 
{ 
		ll x, y; 
		ll g = gcdExtended(a, m, &x, &y); 
		g++;   //this line was added just to remove compiler warning
		ll res = (x%m + m) % m;
		return res;
} 
#define REP(i,a,n) for(ll i=a;i<n;i++)
#define REPd(i,a,n) for(ll i=a; i>=n; i--)
const int MAXN = 2e5+5;
ll facto[MAXN], invfacto[MAXN];
void pre()
{
  facto[0] = invfacto[0] = 1;
  REP(i, 1, MAXN)
  {
	 facto[i] = mymod(i*facto[i-1], M);
	 invfacto[i] = modInverse(facto[i], M);
  }
}
ll nCkM(ll n, ll r)
{
  if(r < 0 || r > n) return 0;
  ll ans = facto[n];
  ans = mymod(ans * invfacto[r], M);
  ans = mymod(ans * invfacto[n-r], M);
  return ans;
}
 


int main(){
    ios_base::sync_with_stdio(false);    // Fast i/o
    cin.tie(NULL);


    int u;
    cin>>u;
    pre();
    F(0,u,g){
      int n,l,r;
      cin>>n>>l>>r;
      if(n&1){
          int a=n/2;
          int m=min(1-l,r-n);
    
          ll z=(m*nCkM(n,a))%M;

          F(m+1,min(max(1-l,r-n),m+a+1)+1,i){
              z=(z+nCkM(n-i+m,a))%M;
          }

          F(max(1-l,r-n)+1,m+a+2,i){
            z=(z+nCkM(n-max(1-l,r-n)-2*(i-max(1-l,r-n))+m,a-i+max(1-l,r-n)))%M;
          }
          a=n/2+1;
          z=(z+m*nCkM(n,a))%M;
          F(m+1,min(max(1-l,r-n),m+a-1)+1,i){
              z=(z+nCkM(n-i+m,a))%M;
          }
          F(max(1-l,r-n)+1,m+a,i){
            z=(z+nCkM(n-max(1-l,r-n)-2*(i-max(1-l,r-n))+m,a-i+max(1-l,r-n)))%M;
          }
        cout<<z<<"\n";
      }
      else{
          int a=n/2;
          int m=min(1-l,r-n);

          ll z=(m*nCkM(n,a))%M;

          F(m+1,min(max(1-l,r-n),m+a)+1,i){
              z=(z+nCkM(n-i+m,a))%M;
          }

          F(max(1-l,r-n)+1,m+a+1,i){
            z=(z+nCkM(n-max(1-l,r-n)-2*(i-max(1-l,r-n))+m,a-i+max(1-l,r-n)))%M;
          }
          
          cout<<z<<"\n";
      }
    }
}