Perfect Permutations
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\)
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,
Visual Basic