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 MAX_N (200000 + 5)
#define LL long long
using namespace std;
const int mod = 1e9 + 7;
int T;
int n, l, r;
int fac[MAX_N], ifac[MAX_N];
int Pow(int x, int y) {
	int res = 1;
	for (; y; y >>= 1, x = (LL)x * x % mod)
		if (y & 1) res = (LL)res * x % mod;
	return res;
}
LL C(int x, int y) {
	return (LL)fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
int main() {
	scanf("%d", &T);
	fac[0] = 1;
	for (int i = 1; i <= 200000; ++i) fac[i] = (LL)fac[i - 1] * i % mod;
	ifac[200000] = Pow(fac[200000], mod - 2);
	for (int i = 200000 - 1; ~i; --i) ifac[i] = (LL)ifac[i + 1] * (i + 1) % mod;
	while (T--) {
		scanf("%d%d%d", &n, &l, &r);
		int ans = 0;
		if (n & 1) {
			ans = (ans + C(n, n / 2) * 2 * min(r - n, 1 - l)) % mod;
			for (int i = min(r - n, 1 - l) + 1; ; ++i) {
				int t1 = max(1, l + i), t2 = min(n, r - i);
				// printf(" --- %d %d\n", t1, t2);
				if (t1 > n / 2 + 2 || t2 < n / 2) break;
				ans = (ans + C(n - (t1 - 1) - (n - t2), n / 2 + 1 - (t1 - 1))) % mod;
				if (n / 2 >= t1 - 1) ans = (ans + C(n - (t1 - 1) - (n - t2), n / 2 - (t1 - 1))) % mod;
				// printf(" --- %d\n", ans);
			}
		}
		else {
			ans = (ans + C(n, n / 2) * min(r - n, 1 - l)) % mod;
			for (int i = min(r - n, 1 - l) + 1; ; ++i) {
				int t1 = max(1, l + i), t2 = min(n, r - i);
				if (t1 > n / 2 + 1 || t2 < n / 2) break;
				ans = (ans + C(n - (t1 - 1) - (n - t2), n / 2 - (t1 - 1))) % mod;
			}
		}

		/*
		if (r - n < 1 - l) {
			if (n & 1) {
				ans = (ans + C(n, n / 2) * 2 * (r - n)) % mod;
				for (int i = n - 1; i >= n / 2; --i) {
					if (1 - (r - i) >= l) {
						ans = (ans + C(i, n / 2 + 1 - (n - i))) % mod;
						if (n / 2 >= n - i) ans = (ans + C(i, n / 2 - (n - i))) % mod;
					}
					else {
						ans = (ans + C(i - (l - (1 - (r - i))), n / 2 + 1 - (n - i))) % mod;
						if (n / 2 >= n - i) ans = (ans + C(i - (l - (1 - (r - i))), n / 2 - (n - i))) % mod;
					}
				}
			} 
			else {
				ans = (ans + C(n, n / 2) * (r - n)) % mod;
				for (int i = n - 1; i >= n / 2; --i) {
					if (1 - (r - i) >= l) {
						ans = (ans + C(i, n / 2 - (n - i))) % mod;
					}
					else {
						ans = (ans + C(i - (l - (1 - (r - i))), n / 2 - (n - i))) % mod;
					}
				}
			}
		}
		else if (r - n == 1 - l) {
			if (n & 1) {
				ans = (ans + C(n, n / 2) * 2 * (r - n)) % mod;
				for (int i = 2; i <= n / 2 + 1; ++i) {
					ans = (ans + C(n - (i - 1) * 2, n / 2 + 1 - (i - 1))) % mod;
					ans = (ans + C(n - (i - 1) * 2, n / 2 - (i - 1))) % mod;
				}
			} 
			else {
				ans = (ans + C(n, n / 2) * (r - n)) % mod;
				for (int i = 2; i <= n / 2 + 1; ++i) {
					ans = (ans + C(n - (i - 1) * 2, n / 2 - (i - 1))) % mod;
				}
			}
		}
		else {
			if (n & 1) {
				ans = (ans + C(n, n / 2) * 2 * (1 - l)) % mod;
				for (int i = 2; i <= n / 2 + 2; ++i) {
					if (n + (i - l) <= r) {
						ans = (ans + C(n - i + 1, n / 2 + 1 - (i - 1))) % mod;
						if (n / 2 >= i - 1) ans = (ans + C(n - i + 1, n / 2 - (i - 1))) % mod;
					}
					else {
						ans = (ans + C(n - i + 1 - (n + (i - l) - r), n / 2 + 1 - (i - 1))) % mod;
						if (n / 2 >= i - 1) ans = (ans + C(n - i + 1 - (n + (i - l) - r), n / 2 - (i - 1))) % mod;
					}
				}
			} 
			else {
				ans = (ans + C(n, n / 2) * 2 * (1 - l)) % mod;
				for (int i = 2; i <= n / 2 + 1; ++i) {
					if (n + (i - l) <= r) {
						ans = (ans + C(n - i + 1, n / 2 - (i - 1))) % mod;
					}
					else {
						ans = (ans + C(n - i + 1 - (n + (i - l) - r), n / 2 - (i - 1))) % mod;
					}
				}
			}
		}*/
		printf("%d\n", ans);
	}
	return 0;
}