1550_D. Excellent Arrays
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]. 
```python
import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7
for t in range(int(input())):
    n, l, r = map(int, input().split())
    F = [0] * (n + 1)
    F[0] = 1
    for i in range(1, n + 1):
        F[i] = i * F[i - 1] % mod
    iF = [0] * (n + 1)
    iF[-1] = pow(F[-1], mod - 2, mod)
    for i in range(n - 1, -1, -1):
        iF[i] = (i + 1) * iF[i + 1] % mod

    def comb(n, m):
        if m < 0 or m > n: return 0
        return F[n] * iF[m] * iF[n - m] % mod

    a, b = l - 1, r - n
    c = min(-a, b)
    ans = comb(n, n // 2) * (1 + n % 2) * c

    d = c + 1
    while True:
        x = min(n, n - (l - 1 + d))
        y = min(n, r - d)
        if x < n // 2 or y < n // 2: break
        ans += comb(x + y - n, n // 2 - (n - y))
        if n % 2:
            # ans += comb(x + y - n, n // 2 - (n - x))
            ans += comb(x + y - n, (n + 1) // 2 - (n - y))
        ans %= mod
        d += 1
    print(ans)

```