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;

typedef long long ll;
typedef pair<int, int> pi;

const ll mod = 1e9 + 7;

ll ipow(ll a, ll p) {
	if (p == 0)
		return 1;

	ll ret = ipow(a, p / 2);
	ret = ret * ret % mod;
	if (p & 1)
		ret = ret * a % mod;

	return ret;
}

ll fac[200005];

ll comb(ll n, ll r) {
	return fac[n] * ipow(fac[r], mod - 2) % mod * ipow(fac[n - r], mod - 2) % mod;
}

int main() {
	fac[0] = 1;
	for (int i = 1; i < 200005; ++i)
		fac[i] = fac[i - 1] * i % mod;

	int T;
	scanf("%d", &T);
	while (T--) {
		ll n, l, r;
		scanf("%lld %lld %lld", &n, &l, &r);

		ll mn = min(-l + 1, r - n);

		ll ans = mn % mod * comb(n, n / 2) * (n % 2 + 1) % mod;
		
		mn++;
		int s = 1, e = n;
		while (true) {
			if (r - 1 < mn || l - n > -mn)
				break;

			while (l - s > -mn)
				s++;
			while (r - e < mn)
				e--;

			int x = n - e, y = s - 1;

			if (x > (n + 1) / 2 || y > (n + 1) / 2)
				break;
			
			if (n % 2 == 0) {
				if (e - s + 1 <= 0)
					ans = (ans + 1) % mod;
				else
					ans = (ans + comb(e - s + 1, n / 2 - x)) % mod;
			}
			else {
				if (e - s + 1 > 0 && x < (n + 1) / 2 && y < (n + 1) / 2) {
					ans = (ans + comb(e - s + 1, n / 2 - x + 1)) % mod;
					ans = (ans + comb(e - s + 1, n / 2 - x)) % mod;
				}
				else if (x < (n + 1) / 2 || y < (n + 1) / 2)
					ans = (ans + 1) % mod;
			}

			mn++;
		}

		printf("%lld\n", ans);
	}

	return 0;
}