Dice Throw Problem Statement

You are provided with D dice, each having F faces numbered 1 to F, inclusive. Your task is to determine the number of possible ways to roll the dice such that the sum of the face-up numbers equals the target sum S.

The result should be returned modulo 10⁹ + 7, as the answer can be large.

Input:

The first line contains an integer T which represents the number of test cases. The following line of each test case consists of three integers D, F, and S which correspond to the number of dice, the number of faces on each die, and the target sum respectively.

Output:

For each test case, output the number of ways to achieve the sum S on a separate line.

Example:

Input:

2
2 6 7
3 6 8

Output:

6
21

Constraints:

• 1 <= T <= 5
• 1 <= D, F <= 50
• 1 <= S <= 10^3
• Time limit: 1 sec

Note:

You are not required to print anything, as it is already handled. You only need to implement the function to return the result.

Follow Up:

Can you solve this using no more than O(S) additional space?