 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