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 <bits/stdc++.h>
#define int long long
#define MOD 1000000007

using namespace std;

int n=0,l=0,r=0;
int fact[300001];

int pw(int a, int b)
{
	int c = 1;
	while (b)
	{
		if (b%2==0)
		{
			a = a*a%MOD;
			b/=2;
		}
		else
		{
			c = c*a%MOD;
			b--;
		}
	}
	return c;
}

int C(int n, int k)
{
	if (k==0 || k==n)
		return 1;
	if (k<0 || k>n)
		return 0;
	//stupid variant for now
	return fact[n]*pw(fact[k], MOD-2)%MOD*pw(fact[n-k], MOD-2)%MOD;
}

int solve_for(int minuses)
{
	int mn = min(abs(1-l), abs(r-n));
	int mx = max(r-1, n-l);
	int res=0;
	/// from 1..mn, all can be + or -
	res+=mn*C(n, minuses)%MOD;
	res%=MOD;
	///check from mn+1 to mx
	for (int d=mn+1; d<=mx; d++)
	{
		int left_both = max(1ll, l+d);
		int right_both = min(n, r-d);	
		if (right_both<left_both-1)
			break;
		int can_both = max(0ll, right_both-left_both+1);
		int have_minuses = n-right_both;
		int want_minuses = minuses-have_minuses;
		if (want_minuses<0)	
			continue;
		res+=C(can_both, want_minuses)%MOD;
		res%=MOD;
	}
	return res;	
}

void solve()
{
	cin >> n >> l >> r;
	int res = solve_for(n/2);
	if (n%2==1)
		res+=solve_for(n/2+1);
	res%=MOD;
	cout << res;
}

signed main(){
	fact[0] = 1;
	for (int i=1; i<=300000; i++)
	{
		fact[i] = fact[i-1]*i;
		fact[i]%=MOD;
	}
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t=1;	
	cin >> t;
	while (t--)
	{
		solve();
		cout << endl;
	}
	return 0;
}
