Excellent Arrays

time limit per test: 2 seconds

memory limit per test: 256 megabytes

Articles

Let’s call an integer array $a_1,a_2,…,$ an good if $ai≠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,…$, an 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:

$[2,1,2];\\ [0,3,2];\\ [2,3,2];\\ [3,0,1].$

Tutorial

code

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;
const int maxn = 1e6+1;

long long M = 1, inv[maxn], mul[maxn], invmul[maxn];
long long C(long long n, long long m) {
    return mul[n] * invmul[m] % mod * invmul[n-m] % mod;
}
void init(int n) {
    inv[1] = invmul[0] = invmul[1] = mul[0] = mul[1] = 1;
    for(int i = 2; i <= n; ++ i) {
        inv[i] = (mod-mod/i) * inv[mod%i] % mod;
        invmul[i] = invmul[i-1] * inv[i] % mod;
        mul[i] = mul[i-1] * i % mod;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    init(maxn-1);
    while(T --) {
        long long n, l, r;
        cin >> n >> l >> r;
        int lk = 1, rk = n, pre = 0;
        long long ans = 0;
        while(true) {
            while (rk >= 0 && r - rk <= 0) rk --;
            while (lk <= n+1 && lk - l <= 0) lk ++;
            if (n & 1) {
                if (lk >= n/2 + 3) break;
                if (rk <= n/2 - 1) break;
                long long k = min(r - rk, lk - l);
                if (lk < n/2 + 2) {
                    ans = (ans + (k-pre)*C(rk-lk+1, n/2-lk+1) % mod) %mod;
                }
                if (rk > n/2) {
                    ans = (ans + (k-pre)*C(rk-lk+1, n/2-lk+2) % mod) %mod;
                }
                pre = k;
                if (r - rk < lk - l) rk --;
                else lk ++;
            }
            else {
                if (lk > n/2+2) break;
                if (rk < n/2) break;
                long long k = min(r - rk, lk - l);
                ans = (ans + (k-pre)*C(rk-lk+1, n/2-lk+1)%mod) % mod;
                if (r - rk < lk - l) rk --;
                else lk ++;
                pre = k;
            }
            
        }
        // if (n&1) ans ++;
        cout << ans << "\n";
    }
    return 0;
}