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 int long long
using namespace std;
const int maxn=2e5+5;
const int lzy=1e9+7;
int T,n,L,R,ans;
namespace sl
{
	int sum1[maxn],sum2[maxn],inv[maxn];
	inline void sager_great_epic()
	{
		sum1[0]=sum2[0]=inv[0]=inv[1]=1;
		for(int i=2;i<maxn;++i)inv[i]=((-lzy/i*inv[lzy%i]%lzy)+lzy)%lzy;
		for(int i=1;i<maxn;++i)sum1[i]=sum1[i-1]*i%lzy,sum2[i]=sum2[i-1]*inv[i]%lzy;
		return;
	}inline int C(int n,int m){return m<0||m>n?0:sum1[n]*sum2[n-m]%lzy*sum2[m]%lzy;}
}
inline void work()
{
	cin>>n>>L>>R;ans=0;int d;
	for(d=min(R-1,n-L);d>=1;--d)
	{
		int l=min(max(0ll,R-d),n),r=min(max(0ll,n-L-d+1),n);
		if(l==n&&r==n){(ans+=((n&1)+1)*d*sl::C(n,n/2))%=lzy;break;}
		if(n&1)(ans+=sl::C(l+r-n,n/2-n+l)+sl::C(l+r-n,n/2+1-n+l))%=lzy;
		else (ans+=sl::C(l+r-n,n/2-n+l))%=lzy;
	}cout<<ans<<"\n";return;
}
signed main()
{
	#ifndef LZVTJL
	ios::sync_with_stdio(0);
	#endif
	sl::sager_great_epic();
	cin>>T;while(T--)work();
}