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;

const int MOD = 1e9+7;

int modadd(int x, int y) {
  int result = x+y;
  if (result >= MOD) result -= MOD;
  return result;
}

int modmult(int x, int y) {
  return (x * int64_t(y)) % MOD;
}

int modaddto(int& x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  return x;
}

int64_t modpow(int64_t b, int64_t e) {
  int64_t ans = 1;
  for (; e; b = b * b % MOD, e /= 2)
    if (e & 1) ans = ans * b % MOD;
  return ans;
}

int64_t gcdExtended(int64_t a, int64_t b, int64_t* x, int64_t* y) { 
  if (a == 0) { 
    *x = 0, *y = 1; 
    return b; 
  } 
  int64_t x1, y1;
  int64_t gcd = gcdExtended(b % a, a, &x1, &y1); 
  *x = y1 - (b / a) * x1; 
  *y = x1;   
  return gcd; 
} 

int64_t modInverse(int64_t a) { 
  int64_t x, y; 
  gcdExtended(a, MOD, &x, &y); 
  return (x % MOD + MOD) % MOD; 
} 

const int MAXN = 200000;
int factorials[MAXN+1];
int invfact[MAXN+1];

int choose(int n, int k) {
  if ((k < 0) || (n < k)) return 0;
  return modmult(factorials[n], modmult(invfact[n-k], invfact[k]));
}

int solve(int n, int l, int r) {
  int wig = 1 + n % 2;
  int half = n / 2;
  int ans = modmult(choose(n, half), modmult(wig, max(0, min(1-l, r-n))));
  for (int x = min(1-l, r-n)+1; x <= min(r-1, n-l); ++x) {
    int n1 = min(n, max(0, l+x-1));
    int n2 = min(n, max(0, n-r+x));
    for (int j = 0; j < wig; ++j) {
      modaddto(ans, choose(n-n1-n2, half+j-n1));
    }
  }
  return ans;
}

void test_case() {
  int n, l, r;
  cin >> n >> l >> r;
  cout << solve(n, l, r) << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  factorials[0] = invfact[0] = 1;
  for (int i = 1; i <= MAXN; ++i) {
    factorials[i] = modmult(factorials[i-1], i);
    invfact[i] = modInverse(factorials[i]);
  }
  int t;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    test_case();
  }
}
