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]. 
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
#include <queue>
#include <sstream>
#include <ctime>
#include <iterator>
#include <string.h>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <fstream>
#include <assert.h>

using namespace std;

long long MOD = 1e9 + 7;
long long fac[200500];

long long mult(long long a, long long b)
{
	return (a * b) % MOD;
}

long long add(long long a, long long b)
{
	return (a + b) % MOD;
}

long long sub(long long a, long long b)
{
	return (a - b + MOD) % MOD;
}

long long binpow(long long a, long long n)
{
	if (n == 0)
		return  1;
	if (n % 2)
		return mult(a, binpow(a, n - 1));
	long long b = binpow(a, n / 2);
	return mult(b, b);
}

long long inv(long long x)
{
	return binpow(x, MOD - 2);
}


void prec()
{
	fac[0] = 1;
	for (size_t i = 1; i < 200400; i++)
	{
		fac[i] = mult(fac[i - 1], i);
	}
}

long long C(int n, int k)
{
	return mult(fac[n], inv(mult(fac[k], fac[n - k])));
}

void solve()
{
	int n, l, r;
	cin >> n >> l >> r;
	long long ans = 0;
	long long f = C(n, n / 2);
	if(n&1)
		f = mult(f, 2);
	int g = min(1-l, r - n);
	int lx = 1 - g, rx = n + g;
	int cnt1 = 0, cnt2 = 0;
	ans += mult(f, g);
	for (long long diff = g + 1; ; diff++)
	{
		long long ma = n + diff;
		long long mi = 1 - diff;
		long long badl = max(0ll, diff - (1-l));
		long long badr = max(0ll, diff - (r-n));
		int h = n - badl - badr;
		if (n%2==0 && (badr > n / 2 || badl > n / 2))
			break;
		if (n & 1 && (badr > n / 2 || badl > n / 2))
		{
			if (badr == badl)
				break;
			badr = max(badr, badl);
			if (badr - 1 != n / 2)
				break;
		}
		if (h < 0)
			break;
		else
		{
			if (n % 2 == 0)
			{
				int q = n / 2;
				q -= badr;
				ans = add(ans, C(h, q));
			}
			else
			{
				int q = n / 2;
				q -= badr;
				ans = add(ans, C(h, q));
				ans = add(ans, C(h, q+1));
			}
		}

	}
	cout << ans << endl;
}


int main()
{
	prec();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}