Count Arrays with Exactly K Inversions

Given two integers (N) and (K), determine the number of arrays (permutations) of length (N) that contain exactly (K) inversions. An inversion is defined as a pair of indices ((i, j)) such that (i < j) and (A[i] > A[j]). Since the number can be extremely large, output the answer modulo (10^9+7). This problem requires you to implement an efficient dynamic programming approach to count the number of valid permutations.

inputFormat

The input begins with an integer (T) representing the number of test cases. Each of the following (T) lines contains two space-separated integers (N) and (K), where (N) is the length of the array and (K) is the required number of inversions.

outputFormat

For each test case, output a single line containing the number of arrays with exactly (K) inversions modulo (10^9+7).## sample

2
3 2
4 3

2
6