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 <cstdio>
#include <iostream>
using namespace std;
#define mod 1000000007
#define int long long
#define maxn 200000
int fac[maxn << 1], inv[maxn << 1];
int T, n, l, r;

int qkpow( int x, int y ) {
	int ans = 1;
	while( y ) {
		if( y & 1 ) ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}

int C( int n, int m ) {
	if( n < 0 || n < m || m < 0 ) return 0;
	else return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

signed main() {
	fac[0] = inv[0] = 1;
	for( int i = 1;i <= maxn;i ++ )
		fac[i] = fac[i - 1] * i % mod;
	inv[maxn] = qkpow( fac[maxn], mod - 2 );
	for( int i = maxn - 1;i;i -- )
		inv[i] = inv[i + 1] * ( i + 1 ) % mod;
	scanf( "%lld", &T );
	while( T -- ) {
		scanf( "%lld %lld %lld", &n, &l, &r );
		int k = min( 1 - l, r - n ), half = n >> 1, ans = 0;
		if( n & 1 ) 
			ans = ( k * C( n, half ) % mod + k * C( n, half + 1 ) % mod ) % mod;
		else
			ans = k * C( n, half );
		while( ++ k ) {
			int L = max( 1ll, l + k ), R = min( r - k, n ), len = R - L + 1;
			if( len < 0 ) break;
			else
				if( n & 1 )
					ans = ( ans + C( len, half - ( L - 1 ) ) + C( len, half - ( L - 1 ) + 1 ) ) % mod;
				else
					ans = ( ans + C( len, half - ( L - 1 ) ) ) % mod;
		}
		printf( "%lld\n", ans );
	}
	return 0;
}