Number of Dice Rolls With Target Sum
You have n dice, and each die has k faces numbered from 1 to k.
Given three integers n, k, and target, return the number of possible ways (out of the k^n total ways) to roll the dice so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 10^9 + 7.
Examples
Input: [1,6,3]
Output: 1
Input: [2,6,7]
Output: 6
Hints
Think about the recurrence relation: `dp[i][j] = sum(dp[i-1][j-f] for f in 1..k)` and how to compute it efficiently with a sliding window to avoid O(n·k²) time.
Observe that for fixed `i`, the values `dp[i][j]` only depend on `dp[i-1][*]`; therefore you can reduce the 2-D table to two 1-D arrays, cutting space to O(k).
To handle the modulo requirement, accumulate the running sum modulo `10⁹ + 7` at each step and use prefix sums or a Fenwick tree to compute each new `dp[i][j]` in O(1) time per cell.
Number of Dice Rolls With Target Sum
You have `n` dice, and each die has `k` faces numbered from `1` to `k`.