All Tracks Problem

Perfect Permutations
Tag(s):

Combinatorics, Dynamic Programming, Hard, Math

Problem
Editorial
Analytics

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 (\(K \le N\)).

Kevin is interested in how many perfect permutations exist. As this number can be very big output it modulo \(1000000007 (10^9 + 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 \(10^9+7\).

Constraints:

  • \(1 \le T \le 100\)
  • \(K \le N\)
  • (10 points): \(1 \le N \le 8, 0 \le K \le 8\)
  • (10 points): \(1 \le N \le 50, 0 \le K \le 50\)
  • (20 points): \(1 \le N \le 1000, 0 \le K \le 1000\)
  • (20 points): \(1 \le N \le 10^9, 0 \le K \le 1000\)
  • (20 points): \(1 \le N \le 10^9, 0 \le K \le 10^5, T = 1\)
  • (20 points): \(1 \le N \le 10^9, 0 \le K \le 10^5\)
SAMPLE INPUT
2
4 2
7 0
SAMPLE OUTPUT
5
1
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).

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

September Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?