All Tracks Math Combinatorics Basics of Combinatorics Problem

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
通知
View All Notifications

?