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 os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192
from bisect import bisect_left


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
import math

N = 200001

# array to store inverse of 1 to N
factorialNumInverse = [None] * (N + 1)

# array to precompute inverse of 1! to N!
naturalNumInverse = [None] * (N + 1)

# array to store factorial of
# first N numbers
fact = [None] * (N + 1)


# Function to precompute inverse of numbers
def InverseofNumber(p):
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, N + 1, 1):
        naturalNumInverse[i] = (naturalNumInverse[p % i] *
                                (p - int(p / i)) % p)


# Function to precompute inverse
# of factorials
def InverseofFactorial(p):
    factorialNumInverse[0] = factorialNumInverse[1] = 1

    # precompute inverse of natural numbers
    for i in range(2, N + 1, 1):
        factorialNumInverse[i] = (naturalNumInverse[i] *
                                  factorialNumInverse[i - 1]) % p


# Function to calculate factorial of 1 to N
def factorial(p):
    fact[0] = 1

    # precompute factorials
    for i in range(1, N + 1):
        fact[i] = (fact[i - 1] * i) % p


# Function to return nCr % p in O(1) time
def Binomial(N, R, p):
    # n C r = n!*inverse(r!)*inverse((n-r)!)
    ans = ((fact[N] * factorialNumInverse[R]) % p *
           factorialNumInverse[N - R]) % p
    return ans


p=10**9+7
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)


t=int(input())
for _ in range(t):




    n,l,r=map(int,input().split())
    mi=min(1-l,r-n)
    ma=max(1-l,r-n)
    ans=0
    if (n%2==0):
        cmi=n//2
        cma=n//2
        ans+=(mi*(fact[n]*factorialNumInverse[cmi]*factorialNumInverse[cmi]))%p
        val=mi+1
        while(cmi>0):
            if val>mi:
                cmi+=-1
            if val>ma:
                cma+=-1

            ans+=(fact[cmi+cma]*factorialNumInverse[cmi]*factorialNumInverse[cma])%p
            val+=1


    else:
        cmi=(n-1)//2
        cma=(n+1)//2
        ans+=(mi*(fact[n]*factorialNumInverse[cmi]*factorialNumInverse[cma]))%p
        val=mi+1
        while(cmi>0 and cma>0):
            if val>mi:
                cmi+=-1
            if val>ma:
                cma+=-1

            ans+=(fact[cmi+cma]*factorialNumInverse[cmi]*factorialNumInverse[cma])%p
            val+=1

        cmi=(n+1)//2
        cma=(n-1)//2
        ans+=(mi*(fact[n]*factorialNumInverse[cmi]*factorialNumInverse[cma]))%p
        val=mi+1
        while(cmi>0 and cma>0):
            if val>mi:
                cmi+=-1
            if val>ma:
                cma+=-1

            ans+=(fact[cmi+cma]*factorialNumInverse[cmi]*factorialNumInverse[cma])%p
            val+=1



    print(ans%p)





    #a=list(map(int,input().split()))





















