Number of Dice Rolls with Target Sum

Roll n dice, each with faces numbered from 1 through k. Count the outcomes whose face values sum to target, and return that count modulo 1000000007. The dice occupy distinct positions: for two dice, rolling (1,2) and (2,1) counts as two outcomes. Return 0 if the target cannot be reached.

Example 1:

Input: n = 2
k = 3
target = 4

Output: 3

Explanation: The ordered outcomes are (1,3), (2,2), and (3,1). Each totals 4, giving three ways.

Example 2:

Input: n = 3
k = 2
target = 3

Output: 1

Explanation: Each die must show 1 to reach the smallest possible sum of 3. Only (1,1,1) qualifies, so return 1.

Example 3:

Input: n = 2
k = 4
target = 9

Output: 0

Explanation: Two four-sided dice can total at most 8. A target of 9 is impossible, so return 0.

Constraints:

• 1 <= n, k <= 30
• 1 <= target <= 1000