Counting Dice Rolls

Difficulty: 1400 5000 ms 128 MB

dp combinatorics

Count the ways to roll D dice, each showing a face 1..F, so the faces sum to exactly T, modulo 10⁹+7.

Input: one line with three integers D, F, T.

Output: the number of ways mod 10⁹+7.

Constraints:

• 1 ≤ D, F ≤ 500
• 1 ≤ T ≤ D·F

Sample Tests

2 6 7

6

1 4 3

1

Read the Editorial