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...

## This Problem was Asked in

Challenge Name

April Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Basic Programming > Implementation
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Data Structures > Advanced Data Structures