Let's call an integer array $a_1, a_2, \dots, a_n$ good if $a_i \neq i$ for each $i$.

Let $F(a)$ be the number of pairs $(i, j)$ ($1 \le i < j \le n$) such that $a_i + a_j = i + j$.

Let's say that an array $a_1, a_2, \dots, a_n$ is excellent if:

$a$ is good;

$l \le a_i \le 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 \le t \le 1000$) — the number of test cases.

The first and only line of each test case contains three integers $n$, $l$, and $r$ ($2 \le n \le 2 \cdot 10^5$; $-10^9 \le l \le 1$; $n \le r \le 10^9$).

It's guaranteed that the sum of $n$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print the number of excellent arrays modulo $10^9 + 7$.


-----Examples-----

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:

$[2, 1, 2]$;

$[0, 3, 2]$;

$[2, 3, 2]$;

$[3, 0, 1]$.

Source: codeforces | Difficulty: HARD
Tags: Constructive algorithms

Combinatorics

Amortized analysis

Sorting

Implementation

Mathematics


Solutions:
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


import sys
from sys import stdin

def modfac(n, MOD):
	f = 1
	factorials = [1]
	for m in range(1, n + 1):
		f *= m
		f %= MOD
		factorials.append(f)
	inv = pow(f, MOD - 2, MOD)
	invs = [1] * (n + 1)
	invs[n] = inv
	for m in range(n, 1, -1):
		inv *= m
		inv %= MOD
		invs[m - 1] = inv
	return (factorials, invs)

def modnCr(n, r):
	return fac[n] * inv[n - r] * inv[r] % mod
mod = 10 ** 9 + 7
(fac, inv) = modfac(300000, mod)
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	(n, l, r) = map(int, stdin.readline().split())
	ans = 0
	dmax = min(1 - l, r - n)
	if dmax >= 0:
		if n % 2 == 0:
			ans += dmax * modnCr(n, n // 2) % mod
		else:
			ans += 2 * dmax * modnCr(n, n // 2) % mod
	nd = dmax + 1
	while True:
		lrist = max(0, l + nd - 1)
		rrist = max(0, n - (r - nd))
		if lrist + rrist > n or min(lrist, rrist) > (n + 1) // 2:
			break
		if n % 2 == 1:
			uprem = n // 2 - lrist
			downrem = (n + 1) // 2 - rrist
			if min(uprem, downrem) >= 0:
				ans += modnCr(uprem + downrem, uprem)
			uprem = (n + 1) // 2 - lrist
			downrem = n // 2 - rrist
			if min(uprem, downrem) >= 0:
				ans += modnCr(uprem + downrem, uprem)
		else:
			uprem = n // 2 - lrist
			downrem = n // 2 - rrist
			if min(uprem, downrem) >= 0:
				ans += modnCr(uprem + downrem, uprem)
		nd += 1
	ANS.append(str(ans % mod))
print('\n'.join(ANS))


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 < 0 or y < 0:
			break
		ans += comb(x + y - n, n // 2 - (n - y))
		if n % 2:
			ans += comb(x + y - n, n // 2 - (n - x))
		ans %= mod
		d += 1
	print(ans)


def readline():
	return map(int, input().split())
MOD = 10 ** 9 + 7
f = [1, 1]

def factorial(x):
	l = len(f)
	while l <= x:
		f.append(f[l - 1] * l % MOD)
		l += 1
	return f[x]

def inv(x):
	return pow(x, -1, MOD)

def comb(n, k):
	return factorial(n) * inv(factorial(k)) % MOD * inv(factorial(n - k)) % MOD

def solve():
	(n, l, r) = readline()
	d = min(r - n, 1 - l)
	h = n >> 1
	partitions = ((h, h + 1), (h + 1, h)) if n & 1 else ((h, h),)
	ans = sum((comb(n, p) for (p, __) in partitions)) * d % MOD
	loop = True
	while loop:
		d += 1
		plus = max(0, d - (1 - l))
		minus = max(0, d - (r - n))
		loop = False
		for (p_, m_) in partitions:
			p = p_ - plus
			m = m_ - minus
			if p >= 0 and m >= 0:
				ans += comb(p + m, p)
				ans %= MOD
				loop = True
	print(ans)

def main():
	t = int(input())
	for __ in range(t):
		solve()
main()


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
inf = 10 ** 16
md = 10 ** 9 + 7

def nCr(com_n, com_r):
	if com_r < 0:
		return 0
	if com_n < com_r:
		return 0
	return fac[com_n] * ifac[com_r] % md * ifac[com_n - com_r] % md
n_max = 200005
fac = [1]
for i in range(1, n_max + 1):
	fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1):
	ifac[i] = ifac[i + 1] * (i + 1) % md

def solve():
	(n, l, r) = LI()
	ans = 0
	mn = max(1, 1 - r, l - n)
	mx = min(1 - l, r - n)
	if mn <= mx:
		if n & 1:
			ans += nCr(n, n // 2) * 2 * (mx - mn + 1 - (mn <= 0 <= mx)) % md
		else:
			ans += nCr(n, n // 2) * (mx - mn + 1 - (mn <= 0 <= mx)) % md
	s = mn - 1
	while s > 0:
		L = max(1, l + s)
		R = min(n, r - s)
		ans += nCr(R - L + 1, n // 2 - L + 1)
		if n & 1:
			ans += nCr(R - L + 1, n // 2 - L + 2)
		s -= 1
	s = mx + 1
	while 1:
		L = max(1, l + s)
		R = min(n, r - s)
		if L > R + 1:
			break
		ans += nCr(R - L + 1, n // 2 - L + 1)
		if n & 1:
			ans += nCr(R - L + 1, n // 2 - L + 2)
		s += 1
		ans %= md
	print(ans)
for testcase in range(II()):
	solve()


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
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

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

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	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)


mod = 10 ** 9 + 7
maxn = int(200000.0 + 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)


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')


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())

def cmb(n, r, mod):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return g1[n] * g2[r] % mod * g2[n - r] % mod
mod = 10 ** 9 + 7
N = 2 * 10 ** 5
g1 = [1] * (N + 1)
g2 = [1] * (N + 1)
inverse = [1] * (N + 1)
for i in range(2, N + 1):
	g1[i] = g1[i - 1] * i % mod
	inverse[i] = -inverse[mod % i] * (mod // i) % mod
	g2[i] = g2[i - 1] * inverse[i] % mod
inverse[0] = 0
for _ in range(int(input())):
	(n, l, r) = mi()
	k = n // 2
	res = 0
	if 1 <= min(r - n, -l - 1):
		if n & 1:
			tmp = cmb(n, k, mod) + cmb(n, k + 1, mod)
			tmp %= mod
		else:
			tmp = cmb(n, k, mod)
		res += tmp * min(r - n, -l - 1) % mod
		res %= mod
		s = min(r - n, -l - 1) + 1
	else:
		s = 1
	for c in range(s, s + n + 2):
		plus = max(0, l - 1 + c)
		minus = max(0, n - max(1, r + 1 - c) + 1)
		if plus + minus > n:
			break
		if n & 1:
			res += cmb(n - plus - minus, k - plus, mod) + cmb(n - plus - minus, k + 1 - plus, mod)
			res %= mod
		else:
			res += cmb(n - plus - minus, k - plus, mod)
			res %= mod
	print(res)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
import bisect, string, math, time, functools, random, fractions
from bisect import *
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby
rep = range
R = range

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def AI():
	return map(int, open(0).read().split())

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def NLI(n):
	return [[int(i) for i in input().split()] for i in range(n)]

def NLI_(n):
	return [[int(i) - 1 for i in input().split()] for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def RLI(n=8, a=1, b=10):
	return [random.randint(a, b) for i in range(n)]

def RI(a=1, b=10):
	return random.randint(a, b)

def INP():
	N = 10
	n = random.randint(1, N)
	a = RLI(n, 1, n)
	return (n, a)

def Rtest(T):
	(case, err) = (0, 0)
	for i in range(T):
		inp = INP()
		a1 = naive(*inp)
		a2 = solve(*inp)
		if a1 != a2:
			print(inp)
			print('naive', a1)
			print('solve', a2)
			err += 1
		case += 1
	print('Tested', case, 'case with', err, 'errors')

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in R(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in R(base ** n):
		s = [tb // base ** bt % base for bt in R(n)]
		rt += [s]
	return rt

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y

def YN(x):
	print(['NO', 'YES'][x])

def Yn(x):
	print('YNeos'[not x::2])

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)

def showf(inp, length=3, end='\n'):
	if show_flg:
		print([' ' * (length - len(str(i))) + str(i) for i in inp], end=end)
mo = 10 ** 9 + 7
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
alp = [chr(ord('a') + i) for i in range(26)]

def gcj(c, x):
	print('Case #{0}:'.format(c + 1), x)
show_flg = False
show_flg = True

class Comb:

	def __init__(self, n, mo=10 ** 9 + 7):
		self.fac = [0] * (n + 1)
		self.inv = [1] * (n + 1)
		self.fac[0] = 1
		self.fact(n)
		for i in range(1, n + 1):
			self.fac[i] = i * self.fac[i - 1] % mo
			self.inv[n] *= i
			self.inv[n] %= mo
		self.inv[n] = pow(self.inv[n], mo - 2, mo)
		for i in range(1, n):
			self.inv[n - i] = self.inv[n - i + 1] * (n - i + 1) % mo
		return

	def fact(self, n):
		return self.fac[n]

	def invf(self, n):
		return self.inv[n]

	def comb(self, x, y):
		if y < 0 or y > x:
			return 0
		return self.fac[x] * self.inv[x - y] * self.inv[y] % mo

	def cat(self, x):
		if x < 0:
			return 0
		return self.fac[2 * x] * self.inv[x] * self.inv[x + 1] % mo
ans = 0
for _ in range(I()):
	(n, l, r) = LI()
	cm = Comb(n + 10)
	if abs(l - n) <= abs(r - 1):
		(l, r) = (n + 1 - r, -l + n + 1)
	m = n // 2
	a = 0
	for x in range(r - n, r - 1 + 1):
		if x == 0:
			continue
		cr = r - x
		cl = min(n, max(0, n - (l + x - 1)))
		if cl >= n and cr >= n and False:
			a += cm.comb(n, m)
			if n % 2 == 1:
				a += cm.comb(n, m + 1)
		else:
			s = n - cl
			t = n - cr
			a += cm.comb(n - s - t, m - s)
			if n % 2 == 1:
				a += cm.comb(n - s - t, m + 1 - s)
	if r - n - 1 > 0:
		a += cm.comb(n, m) * (r - n - 1)
		if n % 2 == 1:
			a += cm.comb(n, m + 1) * (r - n - 1)
	print(a % mo)


def comb(n, r):
	return fact[n] * inv[r] % mod * inv[n - r] % mod if n >= r >= 0 else 0
mod = pow(10, 9) + 7
l = 200005
fact = [1] * (l + 1)
for i in range(1, l + 1):
	fact[i] = i * fact[i - 1] % mod
inv = [1] * (l + 1)
inv[l] = pow(fact[l], mod - 2, mod)
for i in range(l - 1, -1, -1):
	inv[i] = (i + 1) * inv[i + 1] % mod
t = int(input())
for _ in range(t):
	(n, l, r) = map(int, input().split())
	m = min(1 - l, r - n)
	n0 = n // 2 + n % 2
	ans = m * comb(n, n0) % mod * (n % 2 + 1) % mod
	(c1, c2) = (0, 0)
	(l0, r0) = (1, n)
	for _ in range(n):
		m += 1
		if l0 - m < l:
			c1 += 1
		if r0 + m > r:
			c2 += 1
		x = n - c1 - c2
		ans += comb(x, n0 - c1)
		ans %= mod
		if n % 2:
			ans += comb(x, n0 - c2)
			ans %= mod
	print(ans)


M = 10 ** 9 + 7

def choose(n, k):
	p = 1
	for i in range(k):
		p = p * (n - i) * pow(i + 1, -1, M) % M
	return p
for _ in range(int(input())):
	(n, l, r) = map(int, input().split())
	ud = [(n // 2, n // 2)] if n % 2 == 0 else [(n // 2 + 1, n // 2), (n // 2, n // 2 + 1)]
	ans = 0
	for (u, d) in ud:
		(p, prev_n, prev_k) = (0, 0, 0)
		a = min(r - n, 1 - l)
		ans += choose(u + d, u) * a
		ans %= M
		for x in range(min(d + r - n, u + 1 - l), a, -1):
			uu = max(0, min(d, d + r - n - x))
			dd = max(0, min(u, u + 1 - l - x))
			if p == 0:
				p = choose(uu + dd, uu)
			else:
				for i in range(prev_n + 1, uu + dd + 1):
					p = p * i % M
				for i in range(prev_k + 1, uu + 1):
					p = p * pow(i, -1, M) % M
				for i in range(prev_n - prev_k + 1, dd + 1):
					p = p * pow(i, -1, M) % M
			ans = (ans + p) % M
			(prev_n, prev_k) = (uu + dd, uu)
	print(ans)


def main():
	from sys import stdin, setrecursionlimit
	input = stdin.buffer.readline

	def c(n, k):
		if n < k or k < 0:
			return 0
		return f[n] * rev[k] * rev[n - k] % mod
	mod = 10 ** 9 + 7
	f = [1]
	for i in range(1, 200001):
		f.append(f[-1] * i % mod)
	rev = [pow(f[-1], mod - 2, mod)]
	for i in range(200000, 0, -1):
		rev.append(rev[-1] * i % mod)
	rev = rev[::-1]
	for _ in range(int(input())):
		(n, l, r) = map(int, input().split())
		h = n >> 1
		s = min(1 - l, r - n)
		ans = s * (c(n, h) + [0, c(n, h + 1)][n & 1])
		x = s + 1
		while 1:
			ll = max(1, l + x)
			rr = min(n, r - x)
			if rr - ll + 1 < 0:
				break
			ans += c(rr - ll + 1, h - (ll - 1)) + [0, c(rr - ll + 1, h + 1 - (ll - 1))][n & 1]
			x += 1
		print(ans % mod)
main()


N = 200000 + 1
MOD = 10 ** 9 + 7
F = [1] * N
G = [1] * N

def init():
	for i in range(1, N):
		F[i] = F[i - 1] * i % MOD
	G[N - 1] = pow(F[N - 1], MOD - 2, MOD)
	for i in range(N - 2, 0, -1):
		G[i] = G[i + 1] * (i + 1) % MOD

def C(n, m):
	if m > n or m < 0:
		return 0
	return F[n] * G[m] * G[n - m] % MOD

def solve():
	(n, l, r) = list(map(int, input().split()))
	answer = 0
	common_offset = max(min(1 - l, r - n), 0)
	if common_offset:
		answer = common_offset * C(n, n // 2) % MOD
		if n % 2:
			answer += common_offset * C(n, n // 2 + 1) % MOD
	for offset in range(common_offset + 1, min(r - 1, n - l) + 1):
		u = min(r - offset, n) - max(l - offset, 1) + 1
		v = min(r + offset, n) - max(l + offset, 1) + 1
		if u + v < n:
			break
		answer += C(u + v - n, n // 2 - n + v) % MOD
		if n % 2:
			answer += C(u + v - n, n // 2 + 1 - n + v) % MOD
		answer %= MOD
	return answer
init()
for case in range(int(input())):
	print(solve())