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.*;


public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    private static int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }

    private static long nextLong() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (long) in.nval;
    }

    private static String next() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return in.sval;
    }

    public static void main(String[] args) throws Exception {
        int t = nextInt();
        precalc();
        for (int c = 0; c < t; c++) {
            int n = nextInt();
            int l = nextInt();
            int r = nextInt();
            int half = n/2;
            int from = Math.min(1-l,r-n);
            int ans = mul(from,C(n,half));
            if((n&1)==1)ans = norm(ans+mul(from,C(n,half+1)));
            for (int k = from+1; ; k++) {
                int lf = Math.max(1,l+k);
                int rg = Math.min(n,r-k);
                if(rg-lf+1<0)break;
                ans = norm(ans+C(rg-lf+1,half-lf+1));
                if((n&1)==1)ans = norm(ans+C(rg-lf+1,half+1-(lf-1)));
            }
            System.out.println(ans);
        }

    }
    public static int mul(long a,long b){
        return (int) (a*b%mod);
    }
    public static int C(int n, int k) {
        if (k < 0 || n < k)
            return 0;
        return mul(f[n], mul(inf[n - k], inf[k]));
    }
    static int N = 200 * 1000 + 55;
    static int[] f = new int[N];
    static int[] inf = new int[N];
    static int mod = (int) (1e9+7);
    static void precalc() {
        f[0] = inf[0] = 1;
        for (int i = 1; i < N; i++) {
            f[i] = mul(f[i - 1], i);
            inf[i] = binPow(f[i], mod - 2);
        }
    }
    static int binPow(int a, int k) {
        int ans = 1;
        while (k > 0) {
            if ((k & 1)==1)
                ans = mul(ans, a);
            a = mul(a, a);
            k >>= 1;
        }
        return ans;
    }
    static int norm(int a) {
        while (a >= mod)
            a -= mod;
        while (a < 0)
            a += mod;
        return a;
    }
}