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;
namespace math
{

    int inc(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
    int qpow(int a, int x, int mo)
    {
        int res = 1;
        while (x)
        {
            if (x & 1)
                res = 1ll * res * a % mod;
            a = 1ll * a * a % mod;
            x >>= 1;
        }
        return res;
    }
    vector<int> Fac, invFac;
    void Finit(int n)
    {
        Fac.resize(n + 1);
        invFac.resize(n + 1);
        Fac[0] = 1;
        invFac[0] = 1;
        for (int i = 1; i <= n; i++)
            Fac[i] = 1ll * Fac[i - 1] * i % mod;
        invFac[n] = qpow(Fac[n], mod - 2, mod);
        for (int i = n - 1; i >= 1; i--)
            invFac[i] = 1ll * invFac[i + 1] * (i + 1) % mod;
    }
    int C(int n, int m)
    {
        if (m == 0)
            return 1;
        if (n < m || m < 0)
            return 0;
        return (int)(1ll * Fac[n] * invFac[m] % mod * invFac[n - m] % mod);
    }
    int A(int n, int m)
    {
        if (n < m || m < 0)
            return 0;
        return (int)(1ll * Fac[n] * invFac[n - m] % mod);
    }
}
using namespace math;
void solve()
{
    int n, l, r;
    cin >> n >> l >> r;
    Finit(n);
    int ans = 0;
    int up = r - n, dn = 1 - l;
    if (dn < up)
    {
        if (n & 1)
        {
            ans = inc(ans, 2ll * dn * C(n, n / 2) % mod);
        }
        else
        {
            ans = inc(ans, 1ll * dn * C(n, n / 2) % mod);
        }
        for (int i = 1; i <= n; i++)
        {
            int need_add = i;
            int need_del = max(0, dn - up + i);
            if (n - need_del - need_add < 0)
                break;
            ans = inc(ans, 1ll * C(n - need_del - need_add, n / 2 - need_add) % mod);
            if (n & 1)
                ans = inc(ans, 1ll * C(n - need_del - need_add, n / 2 + 1 - need_add) % mod);
        }
    }
    else
    {
        if (n & 1)
        {
            ans = inc(ans, 2ll * up * C(n, n / 2) % mod);
        }
        else
        {
            ans = inc(ans, 1ll * up * C(n, n / 2) % mod);
        }

        for (int i = 1; i <= n; i++)
        {
            int need_del = i;
            int need_add = max(0, up - dn + i);

            if (n - need_del - need_add < 0)
                break;
            ans = inc(ans, 1ll * C(n - need_del - need_add, n / 2 - need_add) % mod);
            if (n & 1)
                ans = inc(ans, 1ll * C(n - need_del - need_add, n / 2 + 1 - need_add) % mod);
            //cout << ans << endl;
        }
    }
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
}