1155

class Solution {
public:
    int numRollsToTarget(int d, int f, int target) {
        int mod = int(1e9)+7;
        vector<int> ways(target+1, 0);
        ways[0] = 1;
        for(int rep = 1; rep <= d; ++rep){
            vector<int> new_ways(target+1);
            for(int sum = 0; sum <= target; sum++) {
                for(int face = 1; face <= f; face++) {
                    if(sum-face >= 0) {
                        new_ways[sum] += ways[sum-face];
                        new_ways[sum] %= mod;
                    }
                }
            }
            ways = new_ways;
        }
        return ways[target];
    }
};