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]. 
import sys
input = lambda: sys.stdin.readline().rstrip()

P = 10 ** 9 + 7
nn = 505050

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P

C = lambda a, b: fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0


def calc(n, l, r):
    a, b = 1 - l, r - n
    aa, bb = r - 1, n - l
    if a > b:
        a, b = b, a
        aa, bb = bb, aa
    re = 0
    if n % 2 == 0:
        re += C(n, n // 2) * a
    else:
        re += (C(n, n // 2) + C(n, n // 2 + 1)) * a
    
    if 0:
        for k in range(a + 1, min(aa, bb, b) + 1):
            if n % 2 == 0:
                re += C(n - (k - a), n // 2 - (k - a))
            else:
                re += C(n - (k - a), n // 2 - (k - a)) + C(n - (k - a), n // 2 + 1 - (k - a))
    elif 0:
        for k in range(1, min(aa, bb, b) - a + 1):
            if n % 2 == 0:
                re += C(n - k, n // 2 - k)
            else:
                re += C(n - k, n // 2 - k) + C(n - k, n // 2 + 1 - k)
    else:
        kk = min(aa, bb, b) - a
        m = n - kk
        mm = n // 2 - kk
        if n % 2 == 0:
            re += C(m + kk, mm + kk - 1)
            re -= C(m, mm - 1)
        else:
            re += C(m + kk, mm + kk - 1)
            re -= C(m, mm - 1)
            re += C(m + kk, mm + 1 + kk - 1)
            re -= C(m, mm)
    if 0:
        for k in range(b + 1, min(aa, bb) + 1):
            if n % 2 == 0:
                re += C(n - (k - a) - (k - b), n // 2 - (k - a))
            else:
                re += C(n - (k - a) - (k - b), n // 2 - (k - a)) + C(n - (k - a) - (k - b), n // 2 + 1 - (k - a))
    else:
        kk = min(aa, bb) - b
        m = n - (kk - a + b)
        if n % 2 == 0:
            for k in range(1, kk + 1):
                re += C(n - (k - a + b) - k, n // 2 - (k - a + b))
        else:
            for k in range(1, kk + 1):
                re += C(n - (k - a + b) - k, n // 2 - (k - a + b)) + C(n - (k - a + b) - k, n // 2 + 1 - (k - a + b))
        
    return re % P

if 1:
    T = int(input())
    for _ in range(T):
        n, l, r = map(int, input().split())
        print(calc(n, l, r))
else:
    from random import randrange
    T = 100
    for _ in range(T):
        n = randrange(4, 20)
        a = randrange(20)
        b = randrange(20)
        l, r = l - a, r + b
        c1 = calc1(n, l, r)
        c2 = calc(n, l, r)
        if c1 != c2:
            print("Error !")
            print("n, l, r =", n, l, r)
            print("c1, c2 =", c1, c2)
    print("END")

