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]. 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
*/
#include<bits/stdc++.h>
using namespace std;


#ifndef ONLINE_JUDGE
  #include "prettyprint.hpp"
#else 
#define dbg(...)
#endif
 
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
 
#define ar array 
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define sz(v) int((v).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,a,b) for(int i = a; i < b; i++)
#define deb(x) cout << #x << "=" << x << endl
#define PI 3.1415926535897932384626
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> > // min heap
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define endl '\n'
 
//typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set; // use less_equal for multiset
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the iterator to kth largest element.(0-based)
 
typedef long long ll; 
typedef long double ld; 
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
 
const  int mxN = 2e5+5;
const  long long INF= 1e18;
const long long mod= 1e9 + 7;

mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers.


ll fact[mxN];

ll power(ll a, ll b) {
	ll res = 1;
	while(b > 0) {
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b /= 2;
	}
	return res;
}

ll inv(ll x) {
	return power(x, mod - 2);
}

void fill() {
	fact[0] = 1;
	rep(i, 1, mxN) {
		fact[i] = fact[i - 1] * 1LL * i % mod;
	}
}

ll ncr(ll n, ll r) {
  if(n < r || r < 0) return 0;
	ll den = fact[r] * fact[n - r] % mod;
	return (fact[n] * inv(den) % mod);
}



void solve() {
  ll n, l, r;
  cin >> n >> l >> r;

  ll val = min(r - n, 1 - l);
  ll half = n / 2;
  ll ans = val % mod * ncr(n, half) % mod;
  if(n & 1) {
    ans += val % mod * ncr(n, half + 1) % mod;
    ans %= mod;
  } 

  while(1) {
    val++;
    ll lf = max(1LL, val + l);
    ll rg = min(n, r - val);

    ll temp = rg - lf + 1;
    if(temp < 0) break;

    ans += ncr(temp, half - (lf - 1));
    ans %= mod;
    if(n & 1) ans += ncr(temp, half + 1 - (lf - 1));
    ans %= mod;
  }
  cout << ans << endl;
}


int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int t = 1;
cin >> t;
fill();
while(t--) {
solve();
}
}

