0

Dice Throws

Difficulty: MEDIUM
Avg. time to solve
35 min
Success Rate
65%

Problem Statement
Suggest Edit

You are given D dice, each having F faces numbered 1 to F, both inclusive. The task is to find the possible number of ways to roll the dice together such that the sum of face-up numbers equal the given target S.

Note:
As the answer can be large, return your answer modulo 10^9  + 7.
Follow Up:
Can you solve this using not more than O(S) extra space?
Input format:
The first line of input contains an integer T denoting the number of queries or test cases. 

The first and the only line of every test case contains 3 integers D, F and S representing the number of dices, the number of faces on each die and the target sum respectively.
Output format:
For each test case, print the number of ways to get the sum S in a separate line. 
Note:
 You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5    
1 <= D <= 50
1 <= F <= 50 
1 <= S <= 10^3

Time limit: 1 second
Sample input 1:
3
2 5 10
1 6 9
2 6 8 
Sample output 1:
1
0
5
Explanation
For test case 1:  
We are given 2 dice with 5 faces numbered 1, 2, 3, 4 and 5.
The only possible way of getting a sum of 10 is when both the die face 5. Hence, the answer is 1.  

For test case 2:
We are given 1 dice with 6 faces numbered 1, 2, 3, 4, 5 and 6.
There is no possible way of getting a sum of 9 with a single die having all the faces less than 9. Hence, the answer is 0. 

For test case 3:
We are given 2 dice with 6 faces numbered 1, 2, 3, 4, 5 and 6.
The possible ways are [{2, 6}, {3, 5}, {4, 4}, {5, 3}, {6, 2}]. Hence, the answer is 5. 
Sample input 2:
2
6 3 8  
2 2 3
Sample output 2:
21
0
Want to solve this problem? Login now to get access to solve the problems