Perfect Permutations

4

21 votes
Combinatorics, Mathematics, Dynamic Programming, Hard
Problem

Kevin calls a permutation perfect if the following conditions holds:

  • Permutation consists of N elements.
  • Permutation has K inversions.
  • Number of inversions isn't bigger than number of elements in permutation (KN).

Kevin is interested in how many perfect permutations exist. As this number can be very big output it modulo 1000000007(109+7).

Input format:

The first line of input will contain an integer T, denoting the number of test cases.
Each of the next T lines contain two integers N and K.

Output format:

For every test case output the number of perfect permutations modulo 109+7.

Constraints:

  • 1T100
  • KN
  • (10 points): 1N8,0K8
  • (10 points): 1N50,0K50
  • (20 points): 1N1000,0K1000
  • (20 points): 1N109,0K1000
  • (20 points): 1N109,0K105,T=1
  • (20 points): 1N109,0K105
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

In the first case perfect permutations are (1,4,2,3) , (1,3,4,2) , (2,1,4,3) , (3,1,2,4) and (2,3,1,4).

Editor Image

?