Pillow Rearrangement

★★★★★

1 votes

Math, Combinatorics, Mathematics, Basics of Combinatorics

Details

Problem

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$

Sample Input

Sample Output

10 
1
3

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For testcase 1: $N=3$ and $K=2$ . The possible final states are (3,0,0), (0,1,2), (0,2,1), (0,3,0), (1,0,2), (1,1,1), (1,2,0), (2,0,1), (2,1,0), (0,0,3) Hence, the answer for this case is 10.

For testcase 2: The possible final states is (1,1). If a pillow is moved from Bed 2 to Bed 1 in the first move, then for the second move, our only option is to move a pillow from Bed 1 to Bed 2. Similarly, if we choose to move a pillow from Bed 1 to Bed 2 in the first move, we obtain the same final state.

For testcase 3: The possible final states are (1,1), (1,0), (0,1). Hence, the answer is 3.

Contributers:

Rohit Pradhan

Divyam Agarwal