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$