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\)
3 3 2 2 2 2 100
10 1 3
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor