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>

using namespace std;

#define int long long

const int mod = 1e9 + 7;
int t, n, l, r;

int qp(int a, int b) {
	if (b == 0) return 1;
	int tmp = qp(a, b / 2);
	if (b % 2 == 0) return tmp * tmp % mod;
	return tmp * tmp % mod * a % mod;
}

int fact[1000001], re_fact[1000001];
int comb(int n, int k) {
	if (k < 0 || n < 0 || k > n) return 0;
	return fact[n] * re_fact[k] % mod * re_fact[n - k] % mod;
}


int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	fact[0] = 1;
	for (int i = 1; i <= 1000000; i++)
		fact[i] = (fact[i - 1] * i) % mod;
	re_fact[1000000] = qp(fact[1000000], mod - 2);
	for (int i = 1000000; i >= 1; i--)
		re_fact[i - 1] = (re_fact[i] * i) % mod;

	cin >> t;
	while (t--) {
		cin >> n >> l >> r;

		int mn = min(r - n + 1, 1 - l + 1);
		int ans = 0;

		if (n % 2)
			(ans += (2 * comb(n, n / 2)) % mod) %= mod;
		else
			(ans += comb(n, n / 2)) %= mod;	
		ans = (mn - 1) * ans % mod;

//		cerr << ans << '\n';

		for (int i = mn; i <= mn + n; i++) {
			int tot = n;
			int lhs = max(0LL, l - (1 - i)), rhs = max(0LL, (n + i) - r);
			tot -= lhs, tot -= rhs;
			if (tot < 0) break;

//			cerr << '?' << tot << ' ' << n/2 << ' ' << lhs << '\n';
			if (n % 2)
				(ans += (comb(tot, n / 2 - lhs) + comb(tot, n / 2 - rhs)) % mod) %= mod;
			else
				(ans += comb(tot, n / 2 - lhs)) %= mod;	
//			cerr << '!' << i << ' ' << ans << '\n';
		}

		cout << ans << '\n';
	}
}