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]. 
mod = 10 ** 9 + 7
maxn = int(2e5 + 10)


Factorial = [1]
for i in range(1, maxn + 1):
    Factorial.append(Factorial[i - 1] * i % mod)

InvFactorial = [1] * len(Factorial)
InvFactorial[-1] = pow(Factorial[-1], mod - 2, mod)
for i in reversed(range(0, maxn)):
    InvFactorial[i] = (InvFactorial[i + 1] * (i + 1)) % mod

def comb(n, k):
    if n < 0 or k < 0 or k > n:
        return 0
    return (((Factorial[n] * InvFactorial[k]) % mod) * InvFactorial[n - k]) % mod


t = int(input())
for _ in range(t):
    n, l, r = map(int, input().split())
    ans = 0
    
    if n % 2 == 0:
        ans = (ans + comb(n, n // 2) * len(range(1, min(1 - l, r - n) + 1))) % mod
    else:
        ans = 2 * (ans + comb(n, n // 2) * len(range(1, min(1 - l, r - n) + 1))) % mod

    for k in range(min(1 - l, r - n) + 1, (r - l + 2) // 2 + 1):
        if min(n, r - k) < max(0, l + k - 1):
            break
        if n % 2 == 0:
            ans = (ans + comb(n - max(0, l + k - 1) - max(0, n - (r - k)), n // 2 - max(0, l + k - 1))) % mod
        else:
            ans = (ans + comb(n - max(0, l + k - 1) - max(0, n - (r - k)), n // 2 - max(0, l + k - 1)) + comb(n - max(0, l + k - 1) - max(0, n - (r - k)), n // 2 + 1 - max(0, l + k - 1))) % mod

    print(ans)