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]. 
import java.util.*;
import java.io.*;
 
public class Sol{
//  ************     n==1  ***************** important test case

public static void main(String []args){
precomp();
int times=ni();while(times-->0){
 int n=ni();int l=ni();int r=ni();
 
 long ans=0l;
 long k=Math.min(1-l,r-n);
 int half=n/2;
 ans=(ans+C(n,half)*k)%mod;
 if(n%2==1)ans=(ans+C(n,half+1)*k)%mod;
 
  
 while(true){
   k++;
   int lf=Math.max(1,(int)(l+k));int rn=Math.min(n,(int)(r-k));
   //out.println(lf+" "+rn);
   if(rn-lf+1<0)break;
  
   ans=(ans+C(rn-lf+1,half-lf+1))%mod;
   if(n%2==1){ans=(ans+C(rn-lf+1,half-lf+2))%mod; }  
 }  
 out.println(ans);

}out.close();}

static int N=200010;
static long inv[]=new long[N];
static long factorial[]=new long[N];

static void precomp(){
 
 inv[0]=1;factorial[0]=1l;
 
 for(long i=1;i<N;i++){factorial[(int)i]=i*factorial[(int)i-1];factorial[(int)i]%=mod;}
 
 for(int i=1;i<N;i++){ inv[i]=power(factorial[i],mod-2);}
 
}

static long C(int n,int r){
   if(r<0 || r>n)return 0l;
   long ans=factorial[n];
   ans=(ans*inv[r])%mod;
   ans=(ans*inv[n-r])%mod;
   return ans;
 }

//-----------------Utility--------------------------------------------
 
static int gcd(int a,int b){if(b==0)return a; return gcd(b,a%b);}
 
static int Max=Integer.MAX_VALUE; static long mod=1000000007;
 
static int v(char c){return (int)(c-'a')+1;}
 
static long factorial(long n){
   long ans=1l;
   long i=1l;
   while(i<=n){ans*=i;ans%=mod;i++;}
   return ans;
 } 

static long inv(long n){
   return power(n,mod-2);
 }
public static long power(long x, long y )
    {
        //0^0 = 1
        long res = 1L;
        x = x%mod;
        while(y > 0)
        {
            if((y&1)==1)
                res = (res*x)%mod;
            y >>= 1;
            x = (x*x)%mod;
        }
        return res;
    }
 
static class Pair implements Comparable<Pair>{
        int x;int y;
 
        public Pair(int x,int y) {
         
          this.x=x;this.y=y;
        }
        @Override
        public int compareTo(Pair p){return Long.compare(y,p.y);}
        //public int compareTo(Pair p){return id-p.id;}
       }

static class Node{
   Node next;
   int id;int value;
   Node(int id,int value){
      id=this.id;this.value=value;next=null;
   }
 }
 
//----------------------I/O---------------------------------------------
 
static InputStream inputStream = System.in;
static OutputStream outputStream = System.out;
static FastReader in=new FastReader(inputStream);
static PrintWriter out=new PrintWriter(outputStream);
 
static class FastReader 
{ 
  BufferedReader br; 
  StringTokenizer st; 
 
        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }
 
  public String next() 
  { 
      while (st == null || !st.hasMoreElements()) 
      { 
          try
          { 
              st = new StringTokenizer(br.readLine()); 
          } 
          catch (IOException  e) 
          { 
              e.printStackTrace(); 
          } 
      } 
      return st.nextToken(); 
  } 
 
  public int nextInt() 
  { 
      return Integer.parseInt(next()); 
  } 
 
  public long nextLong() 
  { 
      return Long.parseLong(next()); 
  } 
 
 public  double nextDouble() 
  { 
      return Double.parseDouble(next()); 
  } 
 
 
  String nextLine() 
  { 
      String str = ""; 
      try
      { 
          str = br.readLine(); 
      } 
      catch (IOException e) 
      { 
          e.printStackTrace(); 
      } 
      return str; 
  } 
}
static int ni() {
        return in.nextInt();
    }
static long nl(){return in.nextLong();}
static String ns(){return in.nextLine();}
 
}