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.io.*;
import java.util.StringTokenizer;

public class CF_1550d{
    static boolean DEBUG= false;
    static int MOD= 1_000_000_007;
    public static final void main(String[] args){
        Kattio io= new Kattio();
        int t= io.getInt();
        while(t-->0){
            int n= io.getInt(), l= io.getInt(), r= io.getInt();
            if(DEBUG) err("n=%d, l=%d, r=%d", n, l, r);
            long ans= 0;
            if(n%2==0){
                // in even case we have 1 pattern with maximum value of F()
                // e.g. 2: +-  4: ++--  6: +++---  8: ++++----
                int maxAdd= r-n/2, maxSub= n/2+1-l, maxChg= Math.min(maxAdd, maxSub);   // max change we can apply to at least one configuration of +maxChg/-maxChg
                int maxAddAll= r-n, maxSubAll= 1-l, maxChgAll= Math.min(maxAddAll, maxSubAll); // max change we can apply to all configurations of +maxChg/-maxChg
                if(DEBUG) err("\tmaxAdd=%d, maxSub=%d => maxChg=%d", maxAdd, maxSub, maxChg );
                if(DEBUG) err("\tmaxAddAll=%d, maxSubAll=%d => maxChgAll=%d", maxAddAll, maxSubAll, maxChgAll );
                
                int howMany= n/2, outOf= n;
                if(maxChgAll>0){
                    ans= Mod.modMult(Mod.modCombinations(outOf, howMany, MOD), maxChgAll, MOD);    // 1..maxChgAll
                    if(DEBUG) err("\t1-%d: adding %d*(%d/%d)=%d", maxChgAll, maxChgAll, outOf, howMany, ans );
                }
                for(int i=maxChgAll+1; i<=maxChg; i++){
                    if(i>maxAddAll && i>maxSubAll){ 
                        outOf= Math.max(0, outOf-2); 
                        howMany= Math.max(0, howMany-1);
                    }else{
                        outOf= Math.max(0, outOf-1); 
                        howMany= Math.max(0, howMany-1);
                    }
                    long add= Mod.modCombinations(outOf, howMany, MOD);
                    if(DEBUG) err("\t%d: adding (%d/%d)=%d", i, outOf, howMany, add );
                    ans= (ans+add)%MOD;
                }
            }else{
                // in odd case we have 2 patterns with maximum value of F() 
                // 3: ++- +--  5: +++-- ++---  7: ++++--- +++----
                int maxAdd1= r-n/2-1, maxSub1= n/2+2-l, maxChg1= Math.min(maxAdd1, maxSub1);   // p1 max change we can apply to at least one configuration of +maxChg/-maxChg
                if(DEBUG) err("\tmaxAdd1=%d, maxSub1=%d => maxChg1=%d", maxAdd1, maxSub1, maxChg1 );
                int maxAdd2= r-n/2, maxSub2= n/2+1-l, maxChg2= Math.min(maxAdd2, maxSub2);   // p2 max change we can apply to at least one configuration of +maxChg/-maxChg
                if(DEBUG) err("\tmaxAdd2=%d, maxSub2=%d => maxChg2=%d", maxAdd2, maxSub2, maxChg2 );
                int maxAddAll= r-n, maxSubAll= 1-l, maxChgAll= Math.min(maxAddAll, maxSubAll); // max change we can apply to all configurations of +maxChg/-maxChg
                if(DEBUG) err("\tmaxAddAll=%d, maxSubAll=%d => maxChgAll=%d", maxAddAll, maxSubAll, maxChgAll );

                int howMany= n/2, outOf= n;
                if(maxChgAll>0){
                    ans= Mod.modMult(Mod.modCombinations(outOf, howMany, MOD), 2*maxChgAll, MOD);    // 1..maxChgAll x 2
                    if(DEBUG) err("\t1-%d: adding 2*%d*(%d/%d)=%d", maxChgAll, maxChgAll, outOf, howMany, ans );
                }
                // pattern 1
                if(DEBUG) err("\tpattern 1");
                outOf= n;
                int howManyAdd= n/2+1, howManySub= n/2;
                for(int i=maxChgAll+1; i<=maxChg1; i++){
                    if(i>maxAddAll && i>maxSubAll){ 
                        outOf= Math.max(0, outOf-2); 
                        howManyAdd= Math.max(0, howManyAdd-1);
                        howManySub= Math.max(0, howManySub-1);
                    }else if(i>maxAddAll){
                        outOf= Math.max(0, outOf-1); 
                        howManySub= Math.max(0, howManySub-1);
                    }else{
                        outOf= Math.max(0, outOf-1); 
                        howManyAdd= Math.max(0, howManyAdd-1);
                    }
                    howMany= Math.min(howManyAdd, howManySub);
                    long add= Mod.modCombinations(outOf, howMany, MOD);
                    if(DEBUG) err("\t%d: adding (%d/%d)=%d", i, outOf, howMany, add );
                    ans= (ans+add)%MOD;
                }
                // pattern 2
                if(DEBUG) err("\tpattern 2");
                outOf= n;
                howManyAdd= n/2; howManySub= n/2+1;
                for(int i=maxChgAll+1; i<=maxChg2; i++){
                    if(i>maxAddAll && i>maxSubAll){ 
                        outOf= Math.max(0, outOf-2); 
                        howManyAdd= Math.max(0, howManyAdd-1);
                        howManySub= Math.max(0, howManySub-1);
                    }else if(i>maxAddAll){
                        outOf= Math.max(0, outOf-1); 
                        howManySub= Math.max(0, howManySub-1);
                    }else{
                        outOf= Math.max(0, outOf-1); 
                        howManyAdd= Math.max(0, howManyAdd-1);
                    }
                    howMany= Math.min(howManyAdd, howManySub);
                    long add= Mod.modCombinations(outOf, howMany, MOD);
                    if(DEBUG) err("\t%d: adding (%d/%d)=%d", i, outOf, howMany, add );
                    ans= (ans+add)%MOD;
                }
            }
            if(DEBUG) err("ans=%d", ans);
            io.println(ans);
        }
        io.close();
    }

    static void err(String format, Object... args){
        System.err.println(String.format(format, args));
    }    

    static class Mod {

        private static final int FACTORIAL_MAX_N = 1_000_000;
        private static final long[] FACTORIALS= new long[FACTORIAL_MAX_N+1];
    
        public static long modFactorial(int n, int m){
            if(n>FACTORIAL_MAX_N)
                throw new RuntimeException(String.format("n=%d is greater than max for factorial(n)", n));
            if(FACTORIALS[n]!=0) return FACTORIALS[n];
            return FACTORIALS[n]= n<2 ? 1L : modMult(n, modFactorial(n-1, m), m);
        }
    
        public static long modCombinations(int n, int k, int m){
            return modDiv(modFactorial(n, m), modMult(modFactorial(n-k, m), modFactorial(k, m), m), m);
        }
    
        public static long modDiv(long a, long b, int m){
            return ((a % m) * modPow(b, m-2, m)) % m;
        }
    
        public static long modMult(long a, long b, int m){
            return ((a % m) * (b % m)) % m;
        }
    
        public static long modPow(long b, long e, int m){
            if(m == 1) return 0;
            long res= 1;
            b= b % m;
            while(e>0){
                if(e%2 == 1) res= (res*b) % m;
                e = e >> 1; // e/= 2
                b = (b*b) % m;
            }
            return res;
        }
    }

    static class Kattio extends PrintWriter {
        private BufferedReader r;
        private String line, token;
        private StringTokenizer st;
    
        public Kattio(){this(System.in);}
        public Kattio(InputStream i){
        super(new BufferedOutputStream(System.out));
            r= new BufferedReader(new InputStreamReader(i));
        }
        public Kattio(InputStream i, OutputStream o){
        super(new BufferedOutputStream(o));
            r= new BufferedReader(new InputStreamReader(i));
        }
        public boolean isLineEnd(){
            return !st.hasMoreTokens();
        }
        public boolean hasMoreTokens(){
            return peekToken()!=null;
        }
        public int getInt(){
            return Integer.parseInt(nextToken());
        }
        public double getDouble(){ 
            return Double.parseDouble(nextToken());
        }
        public long getLong(){
            return Long.parseLong(nextToken());
        }
        public String getWord(){
            return nextToken();
        }
        private String peekToken(){
            if(token==null) try {
                while(st==null || !st.hasMoreTokens()) {
                    line= r.readLine();
                    if(line==null) return null;
                    st= new StringTokenizer(line);
                }
                token= st.nextToken();
            }catch(IOException e){}
            return token;
        }
        private String nextToken() {
            String ans= peekToken();
            token= null;
            return ans;
        }
    }    
}
