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 kn 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 109 + 7.

&nbsp;
Example 1:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.


Example 2:

Input: n = 2, k = 6, target = 7
Output: 6
Explanation: You throw two dice, each with 6 faces.
There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.


Example 3:

Input: n = 30, k = 30, target = 500
Output: 222616187
Explanation: The answer must be returned modulo 109 + 7.


&nbsp;
Constraints:


	1 &lt;= n, k &lt;= 30
	1 &lt;= target &lt;= 1000


class Solution(object):
    def numRollsToTarget(self, n, k, target):
        """
        :type n: int
        :type k: int
        :type target: int
        :rtype: int
        """

        mem = {}

        def dfs(i,currSum):

            if currSum > target:
                return 0

            if i == n:
                if currSum == target:
                    return 1
                return 0

            if (i,currSum) in mem:
                return mem[(i,currSum)]

            ans = 0
            for dicenumber in range(1,k+1):
                ans += dfs(i+1,currSum+dicenumber)

            mem[(i,currSum)] = ans

            return mem[(i,currSum)]

        return dfs(0,0) % (10**9 + 7)
class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        if (target < n || target > n*k) return 0;
        if (n == 1) return 1;

        int[][] dp = new int[n+1][n*k+1];
        for (int i = 1; i<= k; i++) {
            dp[1][i] = 1;
        }
        int mod = 1000000007;
        for (int i = 2; i <= n; i++) {
            for (int j = i; j <= i*k && j <= target; j++) {
                for (int x = 1; x <= k; x++) {
                    if (j-x >= 1) {
                        dp[i][j] += dp[i-1][j-x];
                        if (dp[i][j] >= mod) {
                            dp[i][j] %= mod;
                        }
                    }
                }
            }
        }
        return dp[n][target]%mod;
    }
}
class Solution {
public:
	int dp[31][1001];
	Solution(){
		memset(dp,-1,sizeof(dp));
	}
	int help(int dno,int &tdice,int &tf,int target){
		if(target<0 or dno>tdice) return 0;
		if(target==0 and dno==tdice) {
			return 1;
		}
		if(dp[dno][target]!=-1) return dp[dno][target];
		int ans=0;
		for(int i=1;i<=tf;i++){
			ans=(ans%1000000007+help(dno+1,tdice,tf,target-i)%1000000007)%1000000007;

		}
		return dp[dno][target]=ans;
	}
	int numRollsToTarget(int n, int k, int target) {
	   return help(0,n,k,target);

	}
};
var numRollsToTarget = function(n, k, target) {
    if (n > target || n * k < target) return 0 //target is impossible to reach
    let arr = new Array(k).fill(1), depth = n //start the first layer of Pascal's N-ary Triangle.
    while (depth > 1) { //more layers of Triangle to fill out
        tempArr = [] //next layer of triangle. not done in place as previous layer's array values are needed
        for (let i = 0; i < arr.length + k - 1 && i <= target - n; i++) { //looping is bounded by size of next layer AND how much data we actually need
            let val = ((tempArr[i - 1] || 0) + (arr[i] || 0) - (arr[i - k] || 0)) % (1000000007) //current index value is the sum of K number of previous layer's values, once we hit K we add next and subtract last so we don't have to manually add all K values
            tempArr.push(val)
        }
        arr = tempArr
        depth -= 1
    }
    let ans = arr[target - n] //answer will be in target - nth index
    return ans < 0 ? ans + 1000000007 : ans
};
Number of Dice Rolls With Target Sum