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\)