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 <string.h>
#include <stdio.h>
#include <math.h>
#include <map>
#include <queue>
#include <vector>
#include <numeric>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

#define mp    make_pair
#define pb    push_back
#define F     first
#define S     second
#define ab(x) (((x)<0)?-(x):(x))

#define MOD 1000000007

ll fac[200005];

unsigned long long power(unsigned long long x,
                         int y, int p) {
    unsigned long long res = 1; // Initialize result

    x = x % p; // Update x if it is more than or
    // equal to p

    while (y > 0) {

        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}

// Returns n^(-1) mod p
unsigned long long modInverse(unsigned long long n,
                              int p) {
    return power(n, p - 2, p);
}

// Returns nCr % p using Fermat's little
// theorem.
unsigned long long nCrModPFermat(unsigned long long n,
                                 int r, int p) {
    // If n<r, then nCr should return 0
    if (n < r)
        return 0;
    // Base case
    if (r == 0)
        return 1;


    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
           % p;
}

void solve() {
    int n, s, e;
    cin >> n >> s >> e;

    int k = min(min(ab(s - 1), ab(e - 1)), min(ab(s - n), ab(e - n)));
    int L = 1, R = n, c = k, m1 = n / 2, m2 = (n + 1) / 2;
    ll r = 0;
    for (int i = 0; i <= m2 - m1; i++) {
        int need = m1 + i;
        r = (r + nCrModPFermat(n, need, MOD) * k) % MOD;
    }

    for (k = k + 1;; k++) {
        if (!(s - L <= -k && k <= e - L)) L++;
        if (!(s - R <= -k && k <= e - R)) R--;
        if (R - L + 1 < 0) break;
        int plus = L - 1;
        int minus = n - R;
        if (plus > m2 || minus > m2) break;

        for (int i = 0; i <= m2 - m1; i++) {
            int need = m1 + i - plus;
            r = (r + nCrModPFermat(R - L + 1, need, MOD)) % MOD;
        }
    }

    cout << r << endl;
}

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

    fac[0] = 1;
    for (int i = 1; i <= 200000; i++)
        fac[i] = (fac[i - 1] * i) % MOD;

    int test_case;
    cin >> test_case;
    while (test_case--)
        solve();
}
