All Tracks Math Combinatorics Basics of Combinatorics Problem

Permutations and queries
Tag(s):

Combinatorics, Combinatorics basics, Easy-Medium, Mathematics, dp

Problem
Editorial
Analytics

Define the value of a permutation of \(n\) elements as the number of subintervals where the number of inversions do not exceed \(K\). That is, \(value(P)=\sum_{i=1}^n\sum_{j=i}^n[K\ge \sum_{a=i}^{j-1}\sum_{b=i+1}^j[P_a>P_b]]\).

For example, if \(P=[2,3,1]\), and K=0, then \(value(P)=4\) (the valid intervals are \([1,1],[2,2],[3,3],[1,2]\)).

Now you are given \(Q\) queries. Each query you will receive \(n\) and \(K\), and you need to calculate the sum of value of all permutations of \(1\dots n\).

Input

First line contains an integer \(Q\).

Each of the next \(Q\) lines contain two integers, \(n\) and \(K\).

Output

\(Q\) lines, \(i_{th}\) line contains the answer of \(i_{th}\) query, modulo \(10^9+7\).

Constraints

\(1\le Q\le 100000\)

\(1\le n\le 500 \)

\(0\le K\le 250000\)

SAMPLE INPUT
3
2 0
7 10
10 14
SAMPLE OUTPUT
5
137228
184025758
Explanation

In the first query, \(n=2\) and \(K=0\), so \(value([1,2])=3\) and \(value([2,1])=2\), thus the answer is 5.

Time Limit: 2.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: Bash, 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, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

April Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?