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]. 
// package codeforce.edu111;

import java.io.PrintWriter;
import java.util.Scanner;
//https://codeforces.com/contest/1550/problem/D
//hardest problem I have ever attempted!!!!!
/*
*
*
* */
public class D {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int t = sc.nextInt();

//        int t = 1;
        for (int i = 0; i < t; i++) {
            solve(sc, pw);
        }
        pw.close();
    }
    static int mod = (int) 1e9 + 7;
    static Combinatorial comb = new Combinatorial(mod, (int) 2e5 + 5);
    static void solve(Scanner in, PrintWriter out){
        int n = in.nextInt(), l = in.nextInt(), r = in.nextInt();
        int diff = Math.min(1 - l, r - n);
        long ans = 0;
        if (diff > 0) {
            ans = add(ans, mut(helper(n, 0, 0, n), diff));
        }
        for(int off = diff + 1; true; off++){
            int forceNegative = Math.max(0, n - r + off);
            int forcePositive = Math.max(0, l + off - 1);
            int es = n - forceNegative - forcePositive;
            if (es < 0) break;
            ans = add(ans, helper(es, forcePositive, forceNegative, n));
        }
        out.println(ans);
    }
    static long helper(int rs, int po, int ne, int tot){
        long ans = comb.ncr(rs, tot / 2 - po);
        if (tot % 2 == 1) ans = add(ans, comb.ncr(rs, tot / 2 + 1 - po));
        return ans;
    }

    static long mut(long a, long b){
        return (a * b) % mod;
    }

    static long add(long a, long b){
        return (a + b) % mod;
    }
    static class Combinatorial {

        int MOD;
        int n;
        long[] fact;
        long[] inv;
        long[] ifact;
        public Combinatorial(int mod, int n) {
            this.MOD = mod;
            this.n = n;
            fact = new long[n + 1];
            inv = new long[n + 1];
            ifact = new long[n + 1];
            inv[1] = 1;
            for (int i = 2; i < n; ++i) {
                inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
            }
            fact[0] = ifact[0] = 1;
            for (int i = 1; i < n; ++i) {
                fact[i] = fact[i - 1] * i % MOD;
                ifact[i] = ifact[i - 1] * inv[i] % MOD;
            }

        }

        long ncr(int n, int m){
            if (n < m || m < 0) return 0;
            return fact[n] * ifact[m] % MOD * ifact[n - m] % MOD;
        }
    }

}
