RoAlgo PreOJI 2024 X | dorel

Task

Dorel, a 10th-grade student, has recently started experimenting with algorithms to place $B$ identical balls into $C$ boxes! He tried to analyze how many ways he can place the $B$ balls into the $C$ chosen boxes such that for a chosen constant $K$, the algorithm he wrote on paper does not run indefinitely. His algorithm can be found written in pseudocode below:

pos ← 1
sum ← 0
while pos <= c:
    while sum != k:
        sum ← sum + nrbile[pos] + 1
        pos ← pos + 1
    sum ← 0

Task

For $B$ balls, $C$ boxes, and a constant $K$, determine in how many ways we can place the balls in the boxes such that the algorithm presented above does not run indefinitely. As this number can be very large, Dorel asks you to find the result modulo $10^9+7$.

Input data

The first line of the input file dorel.in contains the number $T$, which represents the number of tests. Then, on the next $T$ lines, there will be 3 numbers $B, C$, and $K$ with the above-mentioned significance. The tests in the input are independent of each other.

Output data

In the file dorel.out, $T$ numbers will be displayed on separate lines, where on line $i$ of the output will be the answer to the $i$-th test modulo $10^9+7$.

Constraints and clarifications

• $1 \leq T \leq 2 \cdot 10^5$
• $1 \leq B, C, K \leq 10^6$
• According to the OJI regulations, the tests will be evaluated individually, so it is not necessary to pass all tests to receive points for the respective subtask.

Example 1

dorel.in

6
3 3 3
1 5 6 
10 10 10
5 8 1
10 2 4
961 423 346

dorel.out

4
5
43758
0
0
434187092

Explanation

For the case $B = 3, C = 3, K = 3$ we have the following valid configurations:

• $0, 1, 2$
• $1, 0, 2$
• $2, 0, 1$
• $2, 1, 0$

For the case $B = 1, C = 5, K = 6$ we have the following valid configurations:

• $1, 0, 0, 0, 0$
• $0, 1, 0, 0, 0$
• $0, 0, 1, 0, 0$
• $0, 0, 0, 1, 0$
• $0, 0, 0, 0, 1$