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++,
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 2.11.8,
Swift,
Visual Basic