좋은 배열 세기

Albert는 최근 재미있는 문제를 풀고 있다. 길이 n+1인 배열 A가 1부터 n-1까지의 정수를 한 번씩 포함하고, n을 두 번 포함하면 배열 A는 좋은 배열이다. 길이가 n+1인 좋은 배열의 개수는 정확히 (n+1)!/2 개 존재한다.

A가 길이 n+1인 좋은 배열이라면, Score(A) 는 다음과 같이 정의 된다: 1 ≤ i < j ≤ n+1 과 A[i] < A[j] 를 만족하는 쌍 (i, j)의 개수. 만약 A = [1, 2, 3, ..., n-1, n, n] 이라면 Score(A)는 (n+2)(n-1)/2로 최대가 되며, A = [n, n, n-1, n-2, ..., 2, 1] 이라면 Score(A) = 0으로 최소가 된다.

Albert는 n과 두 개의 정수 a, b 가 주어졌을 때, a ≤ Score(A) ≤ b 를 만족하는 길이 n+1인 좋은 배열의 개수를 세는 문제를 풀고 싶다. 예를 들어, n = 3, a = 2, b = 3 이라 하자. 총 12개의 좋은 배열 중 a ≤ Score(A) ≤ b를 만족하는 길이 4인 좋은 배열의 개수는 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 (만족)
• A = [2, 1, 3, 3]: Score(A) = 4
• A = [2, 3, 1, 3]: Score(A) = 3 (만족)
• A = [2, 3, 3, 1]: Score(A) = 2 (만족)
• A = [3, 1, 2, 3]: Score(A) = 3 (만족)
• A = [3, 1, 3, 2]: Score(A) = 2 (만족)
• A = [3, 2, 1, 3]: Score(A) = 2 (만족)
• A = [3, 2, 3, 1]: Score(A) = 1
• A = [3, 3, 1, 2]: Score(A) = 1
• A = [3, 3, 2, 1]: Score(A) = 0

입력으로 n, a, b 가 주어졌을 때, a ≤ Score(A) ≤ b 를 만족하는 길이 n+1인 좋은 배열 A의 개수를 출력하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 한 줄에 n, a, b 가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 한 줄에 출력한다.

단, 답이 매우 클 수 있으므로 정답을 109+7 (= 1,000,000,007) 로 나눈 값을 출력한다.

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