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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, 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