Permutations and queries
/

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