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 final class Solution {

    static PrintWriter out = new PrintWriter(System.out);
    static FastReader in = new FastReader();
    static Pair[] moves = new Pair[]{new Pair(-1, 0), new Pair(1, 0), new Pair(0, -1), new Pair(0, 1)};

    public static void main(String[] args) {
        int tt = i();
        int m = (int) 1e9 + 7;
        initializeFactorial((int) 2e5 + 1, m);

        loop:
        while (tt-- > 0) {
            int n = i();
            int l = i();
            int r = i();

            int ll = l - 1;
            int rr = r - n;
            int lc = 0;
            int rc = 0;

            long ans = 0;
            int num = 1;
            if (ll < 0 && rr > 0) {
                num = Math.min(-ll, rr);
                if (n % 2 == 0) {
                    ans += binomialCoefficient(n, n / 2, m);
                } else {
                    ans += binomialCoefficient(n, n / 2, m);
                    ans += binomialCoefficient(n, (n + 1) / 2, m);
                    ans %= m;
                }
                ans *= num;
                ans %= m;
                num++;
            }
            while (true) {
                if (ll > -num) {
                    int d = ll + num;
                    ll -= d;
                    lc += d;
                }
                if (rr < num) {
                    int d = num - rr;
                    rr += d;
                    rc += d;
                }
                if (n % 2 == 0) {
                    if (lc > n / 2 || rc > n / 2) {
                        break;
                    }
                } else {
                    if (lc > (n + 1) / 2 || rc > (n + 1) / 2) {
                        break;
                    }
                    if (lc + rc > n) {
                        break;
                    }
                }
                int len = n - lc - rc;
                if (len == 0) {
                    ans += 1;
                } else {
                    if (n % 2 == 0) {
                        ans += binomialCoefficient(len, n / 2 - lc, m);
                        ans %= m;
                    } else {
                        if (n / 2 - lc >= 0) {
                            ans += binomialCoefficient(len, n / 2 - lc, m);
                            ans %= m;
                        }
                        if (n / 2 - rc >= 0) {
                            ans += binomialCoefficient(len, (n + 1) / 2 - lc, m);
                            ans %= m;
                        }
                    }
                }
                num++;
            }
            out.println(ans);

        }
        out.flush();
    }

    static long[] fac;
    static long[] inv;

    static void initializeFactorial(int n, int mod) {
        fac = new long[n + 1];
        inv = new long[n + 1];
        long[] v = new long[fac.length];
        fac[0] = inv[0] = 1;
        for (int i = 1; i < fac.length; i++) {
            v[i] = i == 1 ? 1 : v[i - mod % i] * (mod / i + 1);
            v[i] %= mod;
            fac[i] = fac[i - 1] * i;
            fac[i] %= mod;
            inv[i] = inv[i - 1] * v[i];
            inv[i] %= mod;
        }
    }

    static int binomialCoefficient(int n, int k, int m) {
        long res = fac[n] * inv[k];
        res %= m;
        res *= inv[n - k];
        return (int) (res % m);
    }

    static void print(char A[]) {
        for (char c : A) {
            out.print(c);
        }
        out.println();
    }

    static void print(boolean A[]) {
        for (boolean c : A) {
            out.print(c + " ");
        }
        out.println();
    }

    static void print(int A[]) {
        for (int c : A) {
            out.print(c + " ");
        }
        out.println();
    }

    static void print(long A[]) {
        for (long i : A) {
            out.print(i + " ");
        }
        out.println();

    }

    static void print(List<Integer> A) {
        for (int a : A) {
            out.print(a + " ");
        }
    }

    static void printYes() {
        out.println("YES");
    }

    static void printNo() {
        out.println("NO");
    }

    static int i() {
        return in.nextInt();
    }

    static long l() {
        return in.nextLong();
    }

    static String s() {
        return in.nextLine();
    }

    static int[][] inputWithIdx(int N) {
        int A[][] = new int[N][2];
        for (int i = 0; i < N; i++) {
            A[i] = new int[]{i, in.nextInt()};
        }
        return A;
    }

    static int[] input(int N) {
        int A[] = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }
        return A;
    }

    static long[] inputLong(int N) {
        long A[] = new long[N];
        for (int i = 0; i < A.length; i++) {
            A[i] = in.nextLong();
        }
        return A;
    }

    static int GCD(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return GCD(b, a % b);
        }
    }

    static long GCD(long a, long b) {
        if (b == 0) {
            return a;
        } else {
            return GCD(b, a % b);
        }
    }

    static long LCM(int a, int b) {
        return (long) a / GCD(a, b) * b;
    }

    static long LCM(long a, long b) {
        return a / GCD(a, b) * b;
    }

    static void shuffleAndSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int rand = (int) (Math.random() * arr.length);
            int temp = arr[rand];
            arr[rand] = arr[i];
            arr[i] = temp;
        }
        Arrays.sort(arr);
    }

    static void shuffleAndSort(int[][] arr, Comparator<? super int[]> comparator) {
        for (int i = 0; i < arr.length; i++) {
            int rand = (int) (Math.random() * arr.length);
            int[] temp = arr[rand];
            arr[rand] = arr[i];
            arr[i] = temp;
        }
        Arrays.sort(arr, comparator);
    }

    static void shuffleAndSort(long[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int rand = (int) (Math.random() * arr.length);
            long temp = arr[rand];
            arr[rand] = arr[i];
            arr[i] = temp;
        }
        Arrays.sort(arr);
    }

    static boolean isPerfectSquare(double number) {
        double sqrt = Math.sqrt(number);
        return ((sqrt - Math.floor(sqrt)) == 0);
    }

    static void swap(int A[], int a, int b) {
        int t = A[a];
        A[a] = A[b];
        A[b] = t;
    }

    static long pow(long a, long b, int mod) {
        long pow = 1;
        long x = a;
        while (b != 0) {
            if ((b & 1) != 0) {
                pow = (pow * x) % mod;
            }
            x = (x * x) % mod;
            b /= 2;
        }
        return pow;
    }

    static long pow(long a, long b) {
        long pow = 1;
        long x = a;
        while (b != 0) {
            if ((b & 1) != 0) {
                pow *= x;
            }
            x = x * x;
            b /= 2;
        }
        return pow;
    }

    static long modInverse(long x, int mod) {
        return pow(x, mod - 2, mod);
    }

    static boolean isPrime(long N) {
        if (N <= 1) {
            return false;
        }
        if (N <= 3) {
            return true;
        }
        if (N % 2 == 0 || N % 3 == 0) {
            return false;
        }
        for (int i = 5; i * i <= N; i = i + 6) {
            if (N % i == 0 || N % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

class Pair {

    int i, j;

    Pair(int i, int j) {
        this.i = i;
        this.j = j;
    }
}

class FastReader {

    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}