There are \(N\) beds numbered from 1 to \(N\). Initially, each bed has a single pillow. Alex performs exactly \(K\) moves. A move can be described as picking a pillow from Bed \(i\) and placing it on Bed \(j\) such that \(i \neq j\). Help Alex to find the number of possible final states of the beds. Two states are considered different if at least one bed has a different number of pillows. Since the answer could be large, compute the answer modulo \(10^9+7\).

Input Format:

The first line contains an integer \(T\), which denotes the number of test cases.
The first line of each test case contains two space-separated integers, \(N\) and \(K\), denoting the number of beds and the number of moves performed respectively.

Output format:

For each test case, compute the number of possible final states after performing the operations described above modulo \(10^9+7\).

Constraints:

\(1 <= T <= 10\)

\(2 <= N <= 10^5\)

\(2 <= K <= 10^9\)