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 FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

string to_string(const string& str) {
  return str;
}

template<typename T>
string to_string(const set<T>& mys) {
  if(mys.empty()) return "{}";
  string ret = "{";
  for(auto el: mys) ret += to_string(el) + ", ";
  ret.pop_back(), ret.pop_back(); // Remove last space and comma
  ret += "}";
  return ret;
}

template<typename T>
string to_string(const pair<T, T>& pr) {
  return "(" + to_string(pr.fi) + "," + to_string(pr.se) + ")";
}

template<typename T>
string to_string(const vector<T>& vc, int w) {
  if(vc.empty()) return "";
  if(w + 1 == vc.size()) return to_string(vc[w]);
  return to_string(vc[w]) + "," + to_string(vc, w + 1);
}

template<typename T>
string to_string(const vector<T>& vc) {
  return "{" + to_string(vc, 0) + "}";
}

void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 2e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20, bs = 29;

ll fastPow(ll a, ll b) {
  ll ret = 1;
  while(b) {
    if(b & 1) ret = ret * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return ret;
}

ll fac[maxN][2], l, r;
int n;

ll ncr(int n, int k) {
  if(k > n) return 0;
  return fac[n][0] * fac[k][1] % MOD * fac[n - k][1] % MOD;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  #ifdef DEBUG
  freopen("input.txt", "r", stdin);
  #endif

  int t;
  cin >> t;
  while(t--) {
    cin >> n >> l >> r;
    l--, r--;
    l -= n - 1;
    l = abs(l);
    r = abs(r);
    if(r > l) swap(l, r);
    fac[0][0] = 1;
    for(ll i = 1; i <= n; i++)
      fac[i][0] = fac[i - 1][0] * i % MOD;
    fac[n][1] = fastPow(fac[n][0], MOD - 2);
    for(ll i = n - 1; i >= 0; i--)
      fac[i][1] = fac[i + 1][1] * (i + 1) % MOD;
    assert(fac[0][1] == 1);

    set<int> keys;
    keys.insert(n / 2);
    keys.insert(n - n / 2);

    ll ans = 0;
    for(auto key: keys) {
      auto defs = r - (n - 1);
      ans = (ans + ncr(n, key) * defs) % MOD;
      ll tempL = l, tempR = r;
      ll limR = tempR - (n - 1);
      int b = n, i = 0;
      for(; tempR > limR; tempR--) {
        while(r - i >= tempR) i++;
        while(b > 0 && tempL >= tempR) tempL--, b--;
        //debug(tempR, b, i);
        auto sz = i - b;
        if(sz < 0) continue;
        int faltan = key - b;
        //debug(faltan);
        if(faltan > sz) continue;
        ans = (ans + ncr(sz, faltan)) % MOD;
        //debug(ans);
      }
    }
    cout << ans << '\n';
  }
}

/*
[2,1,2];
[0,3,2];
[2,3,2];
[3,0,1]

[1,0,1];
[-1,2,1];
[1,2,1];
[2,-1,0]

[1,-1,-1];
[-1,1,-1];
[1,1,-1];
[2,-2,-2]
 */
