All problems

Number of Dice Rolls With Target Sum

Medium · dynamic programming

You roll dice dice. Every die has faces faces, numbered 1 to faces, and the dice can be told apart. So a result is the list of numbers the dice show, die by die: with two dice, showing 1, 2 is a different result from 2, 1.

Count the results whose numbers add up to exactly target.

The count can be very large, so return it modulo 10^9 + 7. If no result adds up to target, return 0.

Examples

Example 1

Input: dice = 1, faces = 6, target = 3

Output: 1

A single die must show a 3, so there is exactly one result.

Example 2

Input: dice = 2, faces = 3, target = 4

Output: 3

The results are (1, 3), (2, 2) and (3, 1).

Example 3

Input: dice = 2, faces = 3, target = 10

Output: 0

Two dice with three faces cannot reach more than 6.

Constraints