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≠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 109+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 109+7.
Constraints:
1<=T<=10
2<=N<=105
2<=K<=109
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.
