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<algorithm>
#include<iostream>
#include<vector>

using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 2e5;

int powMOD(int a, int b) {
	if (b == 1) {
		return a;
	}
	else if(b % 2 == 0) {
		int t = powMOD(a, b / 2);
		return 1LL * t * t % MOD;
	}
	else {
		return 1LL * a * powMOD(a, b - 1) % MOD;
	}
}

inline int C(int n, int k, const vector<int>& fact, const vector<int>& invfact) {
	return (k == 0 ? 1 : 1LL * fact[n] * invfact[n - k] % MOD * invfact[k] % MOD);
}

void solve(const vector<int>& fact, const vector<int>& invfact) {
	int n, l, r;
	cin >> n >> l >> r;

	int res = 0;

	int start = min(r - n, 1 - l);
	if (n % 2 == 0) {
		res += 1LL * start * C(n, n / 2, fact, invfact) % MOD;
	}
	else {
		res += 1LL * start * (1LL * C(n, n / 2, fact, invfact) + C(n, n / 2 + 1, fact, invfact)) % MOD;
	}

	for (int k = 1 + start; ; ++k) {
		int forced_left = max(0, l + k - 1);
		int forced_right = max(0, k - (r - n));
		int free = n - forced_left - forced_right;

		if (free < 0) {
			break;
		}
		else if (free == 0) {
			if (forced_left == n / 2 || forced_right == n / 2) {
				res += 1;
			}
		}
		else {
			if (n % 2 == 0) {
				if(free >= n / 2 - forced_left && n / 2 - forced_left >= 0)
					res = (1LL * res + C(free, n / 2 - forced_left, fact, invfact)) % MOD;
			}
			else {
				if (free >= n / 2 - forced_left && n / 2 - forced_left >= 0)
					res = (1LL * res + C(free, n / 2 - forced_left, fact, invfact)) % MOD;
				if (free >= n / 2 - forced_left + 1 && n / 2 - forced_left + 1 >= 0)
					res = (1LL * res + C(free, n / 2 - forced_left + 1, fact, invfact)) % MOD;
			}
		}
	}

	cout << res % MOD << "\n";
}

int main()
{
	vector<int> fact(MAXN + 1, 1);
	vector<int> invfact(MAXN + 1, 1);
	for (int i = 1; i <= MAXN; ++i) {
		fact[i] = 1LL * fact[i - 1] * i % MOD;
		invfact[i] = powMOD(fact[i], MOD - 2);
	}

	int tt;
	cin >> tt;
	for (int i = 0; i < tt; ++i) {
		solve(fact, invfact);
	}
}
