Count Dice Rolls With Total

You are given integers n, faces, and total.

Each of the n dice has faces faces, showing a value from 1 to faces. Return the number of ways to throw all n dice so that the values add up to total. The dice are distinguishable, so rolling a 1 then a 2 counts separately from rolling a 2 then a 1. If total cannot be reached, return 0.

Mod the result by 10 ** 9 + 7.

Examples

Example 1

Input: n = 1, faces = 6, total = 3
Output: 1
Explanation: With one die, the only way to get a total of 3 is to roll a 3.

Example 2

Input: n = 2, faces = 6, total = 7
Output: 6
Explanation: The six ways are (1,6), (2,5), (3,4), (4,3), (5,2), and (6,1).

Example 3

Input: n = 2, faces = 5, total = 10
Output: 1
Explanation: The only way is to roll a 5 on both dice.