Counting Good Arrays

Albert is working on an interesting problem. An array A of length n+1 is a good array if it contains each of the integers from 1 to n-1 exactly once and contains n twice. The number of good arrays of length n+1 is exactly (n+1)!/2.

If A is a good array of length n+1, Score(A) is defined as follows: the number of pairs (i, j) with 1 ≤ i < j ≤ n+1 and A[i] < A[j]. If A = [1, 2, 3, ..., n-1, n, n], then Score(A) is maximized at (n+2)(n-1)/2, and if A = [n, n, n-1, n-2, ..., 2, 1], then Score(A) = 0, the minimum.

Given n and two integers a and b, Albert wants to count the number of good arrays of length n+1 with a ≤ Score(A) ≤ b. For example, let n = 3, a = 2, b = 3. Of the 12 good arrays in total, the number of good arrays of length 4 with a ≤ Score(A) ≤ b is 6.

• A = [1, 2, 3, 3]: Score(A) = 5
• A = [1, 3, 2, 3]: Score(A) = 4
• A = [1, 3, 3, 2]: Score(A) = 3 (counts)
• A = [2, 1, 3, 3]: Score(A) = 4
• A = [2, 3, 1, 3]: Score(A) = 3 (counts)
• A = [2, 3, 3, 1]: Score(A) = 2 (counts)
• A = [3, 1, 2, 3]: Score(A) = 3 (counts)
• A = [3, 1, 3, 2]: Score(A) = 2 (counts)
• A = [3, 2, 1, 3]: Score(A) = 2 (counts)
• A = [3, 2, 3, 1]: Score(A) = 1
• A = [3, 3, 1, 2]: Score(A) = 1
• A = [3, 3, 2, 1]: Score(A) = 0

Given n, a, and b as input, write a program that prints the number of good arrays A of length n+1 with a ≤ Score(A) ≤ b.

The first line gives the number of test cases T.

Each test case is given on one line as n, a, b separated by spaces.

Print the answer for each test case on one line.

Since the answer can be very large, print the answer modulo 109+7 (= 1,000,000,007).

• 1 ≤ T ≤ 10,000
• 2 ≤ n ≤ 1,000
• 0 ≤ a ≤ b ≤ 1,000