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]. 
﻿//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,@@@@@@@@@@@@@@@@@@@%@@@@@%@@@@@@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,&@@@@@@@@@@@@@@@@@@@@@%@@@@@%@@@@@@%@@@%&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,@@@@,,,,@@@@@@@@@@@@@@@@@%@@@@@%@@@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,@@@@@@@@@@@@@@@@@%%@@@@@%@@@@@@%%&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,@@@@@@@@@@@@@@@@@@@%%@@@@@%%@@@@@%%%&@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,#@,,*@@@@@@@@@@@@@@@@@%%%@@@@@%@@@@@%%%%&@@@@@@%@@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,@@@@@@@@@@@@@@@@@@%%%@@@@@%%@@@@&%%%%%@@%@@@@&@@@@%%&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,@@@@@@@@@@@@@@@@@@%%%@@@@@%%%@@@@%%%%%%@@%@@@@%@@@@%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,@@@@@@@@@@@@@@@@@@@%%%@@@@@%%%@@@%%%%%%%@@%@@@@%%@@@%%%&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,@@@@@@@@@@%@@@@@@@@%%%@@@@%@%%%@@@%%%%%%%@&%&%@@&%@@&%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,@@@@@@%@@@%@@@@@@@@%%%%@@@@%%%%%@@%%%%%%%%%%%%%%@@%%@%%%%%@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,@@@@@@%@@@%@@@@@@@@%%%%@@@%%%%%%@@%%%%%%%%%%%%%%&@%%@%%%%%@@@@@@@@&@@@@%@@@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,@@@@@@%@@@%%@@@&@@@%%%%@@@@%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%%%&@@&%@@@@@@@@%%&@@@@@%%@@@@%%@@@@@&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,@@@,@@%%@@@%%@@@%@@@%%%%@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%&@@@%&@@@@@@@%%%%@@@@%%%@@@%%%@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,@@@,*@@%%@@%%@@@%%@@%%%%%@@@%%%%%%%%%%%%#%%%%%%%%%%%%%%%%%%%%@@@@%%@@@&@@@#%%%%@@@@%%@@@%%%%@@%%%@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,@,@(,@@@%&@@%%@@@%%@@%%%%%@@@%%%%%%%%%%%%/%%%%%%%%%%%%%%%%%%%%@@@@%%%@@%@@@//%%%%@@@@%%@@%%%%@@%%%@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,(,,,@,,@@%%@@%%%@%%%%@@%%%%%@@@%%%%%%%%%%%///%%%/(%%%%%%%%%%%%%%@@@@@%%%@%@@@&//#%#&@@@%%%%%%%%%@%%%%@@@%%@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,/,,@@%%@@%%%%%%%%@%%%%%%%@@%%%%#/%%%%%///%%%//(%(%%%%%%%%%%/&@@@@(%%&%%@@@////%/@@@@%%%%%%%%&%%%%@@@%%@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,@@%%%&%%%%%%%%@%%%%%%%@%%%%%///%%%%///%%%///#(/%%%%%%%///%@@@@/%%%%%@@.     ( .@@%%%%%%%%%%%%%%@%%%@@@@%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,@@%%%%%%%%%%%%@%%%%%%%@%#%%#///#%%%/////%#///#//%%%%%#///&@@@@//&%%*@            %%%%%%%%%%%%%%@%%%%%@@%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,#%%%%%%%%%%%%%%%%%%%%%%//#%/////%*%*/////////////%%/%////@@@/@@@@ %(     ,,       %%( #%%%%%%%%%%%%%%%@%%%@%@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,%%%%%%%%%%%%%%%%%%%%%%///%  (((((((((((, ///////(%//////@@///@@@        ,,       %% //%%%%%%%%%%%%%%%%%%%@@%@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,%%%%%%%%%%%%%%%%%%%%%/* %((@@@@@./(.@@@@#( /////#//////(////@@@                 #//@/%%%%%%%%%%%%%%%%%%%@@@%@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,%%%%%%%%%%%%%%%%%%%%// ((@@@@@@@@.%@@@@@@(/////////@///#@@#/////@@@        %////@@@/%%%%%%%%%%%%%%%%%%@@@@%@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,#%%%%%%%%%%%%%%%%%%/%///@@(@@@@@@@@@@@@(@@@/@@@/////@@/@@@@@@////////(@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,%%%,%%,%%%%%%%%%%%%%#////@@@@@@@@@@@&#///////////////#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%%%//%%%%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,(,,,%,,,%%%%%%%%%%%%%%/@@/@@&//////////////////////////@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%@%%%%///%%%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,*,,,,,%%%%%%#%%%%%%%@@@@@@//////////////////////////@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@/%#%/////%%%%%%&@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,%,%%%%//%%%%%%%@@@@@//////////////////////////&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@//////@@@@@%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,%,%%%/////%/%%@%@@@@@(/////////////////////////@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@////%@@@@@@@@@%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,#,%%%,,////////@@@@@@@@////////////////////////%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@(/&@@@/#@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,///////@@@@@@@@////////////////////////@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@//////@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,/////@@@@@@@@@///////////////////////@@@@@@@@@@@@@@@@@@@#@@@@@@@@@@/%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,##////@@@@@@@@@@@@@//////////////////@@@@@@@@@@@@@@@@@(/@@@@@@@@@#(%%@@&%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,(#,,,##,*@@@@@@@@@///////////////////////////////////@@@@@@@@@@@@/%%%%@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,##,,,@@@@@@@&//////////@@@@@@@@@@@@@&//@@@@@@@@@@@@@@@@@@@/%%%%%%@@@@@@&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,#,,,#%@@@@@@(//////////////@@@@@@@@@@@@@@@@@@@@@@@@@@@@/%%%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,#,,,####@@@@@@/////////////////%%#///////@@@@@@@@@@@@///%%%%@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,#,#####@@@@@/////////////////(@@@@@@@@@@@@@@@@(/////%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,*,,#####(//@@@@//////////////@@@@@@@@@@@@@@&////////% %         &@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,           # ###//////@@&///////////@@@@@@@@@@@///////////.% #              @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,            ###/////////@/////////@@@@@@@/////////////// %              @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,                 , ////////////////////////////////,  ///                /@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,  .                                                                        @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,                                                                        @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,                                                                       @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,                                                                        @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,                                                                         @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,                                                                                 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,,,,                                                                                           @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,,,,,                                                                                                 @@@@@@@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,,,,,                                                                                                          %@@@@@@@@@@@@@@@@@@@@@
//,,,,,,,,,,,,,,,,,,                                                                                                                  *@@@@@@@@@@@@@@@@@
//,                                                                                                                                          .@@@@@@@@@@
//                                                                                                                                                      
// 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,abm,mmx,avx,avx2,popcnt")
#pragma comment(linker, "/STACK:150777216")
#include <set>
#include <map>
#include <deque>
#include <string>
#include <cstdint>
#include <cmath>
#include <queue>
#include <cassert>
#include <random>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <time.h>//////////////
#include <ctime>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <complex>
#include <chrono>
#include <unordered_set>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define all(a) (a).begin(), (a).end()
#define pbc push_back
#define pob pop_back()
#define vin(a) for (auto& i : a) cin >> i
#define sp system("pause")
#define mp make_pair
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

mt19937 rnd(123);
template<typename T1, typename T2>
inline void chkmin(T1& x, const T2& y)
{
	if (y < x) x = y;
}

template<typename T1, typename T2>
inline void chkmax(T1& x, const T2& y)
{
	if (x < y) x = y;
}

const int MAXN = 4e5 + 228;
int mod = 1000000007;
int mul(int a, int b)
{
	return 1ll * a * b % mod;
}
int add(int a, int b)
{
	if (a + b >= mod) return a + b - mod;
	return a + b;
}
int sub(int a, int b)
{
	if (a - b < 0) return a - b + mod;
	return a - b;
}
int binpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
int inv(int x)
{
	return binpow(x, mod - 2);
}
int fact[MAXN]; int rfact[MAXN];
int cnk(int n, int k)
{
	if (k<0 || k>n) return 0;
	return mul(fact[n], mul(rfact[k], rfact[n - k]));
}
signed main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cout.precision(20), cout.setf(ios::fixed);
	fact[0] = 1;
	for (int i = 1; i < MAXN; ++i) fact[i] = mul(fact[i - 1], i);
	rfact[MAXN - 1] = inv(fact[MAXN - 1]);
	for (int i = MAXN - 2; i >= 0; --i) rfact[i] = mul(rfact[i + 1], i + 1);
	int t;
	cin >> t;
	while (t--)
	{
		int n, l, r;
		cin >> n >> l >> r;
		int xx = min(1 - l, r - n);
		int ans = 0;
		int nw = 0;
		if (n % 2) nw = add(cnk(n, n / 2), cnk(n, n / 2));
		else nw = add(nw, cnk(n, n / 2));
		ans = add(ans, mul(nw, xx));
		for (int k = xx + 1,tk =0;tk<=2*n; ++k,++tk)
		{
			int fs = max(0, l + k - 1);
			int ti = min(n, r - k);
			ti = n - ti;
			int lft = n - fs - ti;
			int gg = max(fs, ti) - min(fs, ti);
			if (n % 2 == 0)
			{
				if (fs > n / 2) break;
				if (ti > n / 2) break;
				ans = add(ans, cnk(lft, n / 2 - fs));
			}
			else
			{
				int addon = 0;
				addon = add(addon, cnk(lft, n / 2 - fs));
				addon = add(addon, cnk(lft, n / 2 + 1 - fs));
				//if (!addon) break;
				ans = add(ans, addon);
			}
		}
		cout << ans << endl;
	}
	//sp;
}