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 io,os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

M = 10**9+7
MAX = 10**6+1
factor = [1]*MAX
for i in range(1,MAX):
    factor[i] = (factor[i-1]*i)%M


def fastfrac(a,b,M):
    numb = pow(b,M-2,M)
    return ((a%M)*(numb%M))%M





def comb(m,n):
    if n<0 or m<0: return 0
    num1 = factor[m]
    num2 = factor[n]
    num3 = factor[m-n]
    num = fastfrac(num1,num2,M)
    num = fastfrac(num,num3,M)
    return num


def getnum(n,mustl,mustr):
    if mustl>mustr:  mustl,mustr = mustr,mustl
    
    if mustr>n//2+1: return 0



    output = 0
    freedom = n - mustl - mustr
    if n%2==0:
        pick = n//2 - mustr
        output += comb(freedom,pick)
        output = output %M
    else:
        pick1 = n//2 - mustr
        pick2 = n//2 - mustr + 1
        output += comb(freedom,pick1)
        output = output %M
        output += comb(freedom,pick2)
        output = output %M
      

    return output
        
        





T = int(input())
t = 1

while t<=T:

    n,l,r = map(int,input().split())


    lleft = l - 1
    rleft = r - 1
    lright = l - n
    rright = r - n



    ans = min(-lleft,rright) * getnum(n,0,0)
    ans = ans%M




    diff = abs(-lleft-rright)

    mustl = 0
    mustr = 0
    while diff>0:
        mustr += 1
        ans += getnum(n,mustl,mustr)
        if mustr>n: break
        ans = ans%M
        diff -= 1

    while mustr<n:
        mustl += 1
        mustr += 1
        ans += getnum(n,mustl,mustr)
        ans = ans%M




        
    
        



    print(ans)


              

 
 
    
    t += 1
