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>
//#include <atcoder/all>
#define int long long
#define rep(i,a) for (int i = 0; i < (a); i++ )
#define Rep(i,start,a) for (int i = start; i < (a); i++ )
#define ALL(vec) (vec).begin(), (vec).end()
#define Sort(vec) sort((vec).begin(), (vec).end()) // 小さい順
#define SORT(vec) sort((vec).begin(), (vec).end(), [](auto a, auto b){return a>b;}) // 大きい順
#define SORTll(vec) sort((vec).begin(), (vec).end(), [](long long a, long long b){return a>b;}) // 大きい順
#define debug(x) cerr << #x << " = " << (x) << endl
#define Bit(s,k) (s>>k)&1
#define VI vector<int>
#define VLL vector<long long>
#define PII pair<int,int>
#define VPII vector<PII>
#define VB vector<bool>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define Graph vector<vector<int>>
#define PB emplace_back
#define USI unordered_set<int>
#define Maze vector<string>
#define Pqueue priority_queue
#define MP make_pair
#define WeightedGraph vector<vector<pair<int,ll>>> // parent, (to, cost)

#define vecdebug(vec) {cerr << #vec << " = [" ; for(auto x : (vec)){cerr << (x) << ", ";} cerr << "]" << endl; }
#define vdebug(vec,i) cerr << #vec << "[" << (i) << "] = " << (vec)[(i)] << endl
#define vvdebug(vec,i,j) cerr << #vec << "[" << (i) << "][" << (j) << "] = " << (vec)[(i)][(j)] << endl
#define vvvdebug(vec,i,j,k) cerr << #vec << "[" << (i) << "][" << (j) << "][" << (k) <<"] = " << (vec)[(i)][(j)][(k)] << endl
#define pdebug(p) cerr << #p << " = [" << (p).first << ", " << (p).second << "]" << endl

typedef long long ll;
typedef long double ld;

const int mod = 998244353;
//const int MOD = 1000000007;
const ll INFLL = (1LL << 60) -1;
const int INF = (1 << 30) -1;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const long double pi = 2*asin(1);

using namespace std;
//using namespace atcoder;

//using mint = modint1000000007;
//using mint = modint998244353;
//using mint = modint998244353;
//using mint = static_modint<7>;


template<typename T>
inline void chmin(T &x, T y){if(x>y) x=y;}

template<typename T>
inline void chmax(T &x, T y){if(x<y) x=y;}

inline int tonum(char X){
  if(X >= 'A' && X <= 'Z') return 26 + (int)(X-'A');
  return (int)(X - 'a');
}

inline int ctoi(char x){return (int)(x-'0');}

template<typename T>
T Max(T x, T y){if(x>y) return x; return y;}

template<typename T>
T Min(T x, T y){if(x<y) return x; return y;}

inline int tochar(int n){return (char)('a' + n);}

template<typename T>
inline T ABS(T n){if(n<0) return -n; return n;}

ll GCD(ll a, ll b){if(a%b==0) return b; return GCD(b,a%b);}

ll LCM(ll a, ll b){return a / GCD(a,b) *b;}







// not ACL version

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void modcombinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long modcomb(long long n, long long k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


void solve(){
  int n, l, r; cin >> n >> l >> r;
  int a = r - n;
  int b = 1 - l;
  if(a > b) swap(a,b);
  
  //cout << "a : " << a << " b : " << b << endl;
  
  int ans = 0;

  if(n%2 == 0){
    ans = (a%MOD) * modcomb(n, n/2);
    ans %= MOD;

    Rep(d,a+2,n+a+1){
      //  cout << "ans : " << ans << endl;
      int cb = modcomb(n - Max(0LL, d-a-1) - Max(0LL, d-b-1) , n/2 - Max(0LL, d-a-1));
      if(cb == 0) break;
      ans = (ans + cb) % MOD;
    }
  }

  if(n%2 == 1){
    ans = (a%MOD) * modcomb(n, n/2) + (a%MOD) * modcomb(n,1 + n/2);
    ans %= MOD;

    Rep(d,a+2,n+a+1){
      //cout << "ans : " << ans << endl;
      int cb1 = modcomb(n - Max(0LL, d-a-1) - Max(0LL, d-b-1) , n/2 - Max(0LL, d-a-1));
      int cb2 = modcomb(n - Max(0LL, d-a-1) - Max(0LL, d-b-1) , 1 + n/2 - Max(0LL, d-a-1));
      //cout << "cb1 : " << cb1 << endl;
      //cout << "cb2 : " << cb2 << endl;
      if(cb1 == 0 && cb2 == 0) break;
      ans = (ans + cb1 + cb2) % MOD;
    }
  }

  cout << ans << endl;
}

signed main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(16);


  modcombinit();
  int Query; cin >> Query; rep(_,Query)
  solve();
}