You have d dice, and each die has f faces numbered 1, 2, ..., f.
Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.
 
Example 1:
Input: d = 1, f = 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: d = 2, f = 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: d = 2, f = 5, target = 10
Output: 1
Explanation: 
You throw two dice, each with 5 faces.  There is only one way to get a sum of 10: 5+5.

Example 4:
Input: d = 1, f = 2, target = 3
Output: 0
Explanation: 
You throw one die with 2 faces.  There is no way to get a sum of 3.

Example 5:
Input: d = 30, f = 30, target = 500
Output: 222616187
Explanation: 
The answer must be returned modulo 10^9 + 7.

 
Constraints:

1 <= d, f <= 30
1 <= target <= 1000

Difficulty: interview

Starter code:

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        

Solutions:
["from math import comb\nfrom math import pow\nclass Solution:\n\n        \n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if(target < d*1 or target > d*f ):\n            return 0\n        target = target - d\n        sum = 0\n        i = 0\n        j=0\n        while(i <= target):\n            y = target - i\n            if(j%2 == 0):\n            \n                sum =int( (sum +  comb(d, j) * comb(y+d-1,y)) )\n            else:\n                sum =int( (sum -  comb(d, j) * comb(y+d-1,y)))\n            #print( comb(d, j) * comb(y+d-1,y))\n            #print('i ={} y= {} sum={}  '.format(i,y,sum))\n            j=j+1\n            i = i + f\n            \n        #print(sum)\n        return int(sum) % 1000000007\n", "class Solution:\n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target < d or target > d * f:\n            return 0\n        \n        total_sum = 0\n        cache_sum = []\n        \n        if target > d * (1 + f) / 2:\n            target = d * (1 + f) - target\n        \n        for i in range(target, -1, -1):\n            num = 0 if i > f else 1\n            total_sum += num; \n            cache_sum.append(total_sum)\n        cache_sum = cache_sum[::-1]\n        cache_sum[0] = cache_sum[1]\n        \n        for i in range(2, d+1):\n            total_sum = 0\n            for j in range(target, -1, -1):\n                total_sum += cache_sum[max(j-f, 0)] - cache_sum[j]\n                cache_sum[j] = total_sum\n        return cache_sum[-1] % (10**9+7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        @lru_cache(None)\n        def solve(s,t):\n            if s == 0:\n                if t == 0:return 1\n                return 0\n            ans = 0\n            for i in range(1,f+1):\n                if t >= i:\n                    ans += solve(s - 1,t - i)\n            return ans\n        return solve(d,target) % (10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # dp[d][target] = sum(dp[d-1][target - w]) w in 1-f\n        dp = {0: 1}\n        MOD = 10 ** 9 + 7\n        for i in range(d):\n            ndp = {}\n            for k, v in list(dp.items()):\n                for w in range(1, f+1):\n                    if k + w <= target: \n                        ndp[k+w] = (ndp.get(k+w, 0) + dp[k] ) % MOD\n            dp = ndp.copy()\n        return dp.get(target, 0)\n", "class Solution:\n    seen = {}\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        results = {}\n        results[1] = {}\n        for i in range(1, min(f, target) + 1):\n            results[1][i] = 1\n        for i in range(2, d+1):\n            results[i] = {}\n            for val, times in list(results[i-1].items()):\n                for j in range(1, min(f, target) + 1):\n                    results[i][j+val] = results[i].get(j+val, 0) + times\n                    \n        return results[d].get(target, 0) % 1000000007\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n      return memoization(d,f,target)\n\n# thank goodness that dices have orders (they are different dices)      \n# d = 2, f = 3, t = 4\n# (1,3), (2,2), (3,1)\n# note that (1,3) and (3,1) are different ways (by definition in this example)\n# TODO: what if they are exchangable?\n\n# sol:\n# f(d, f, t) = f(d-1, f, t-v) for v ...\n\nfrom functools import lru_cache\nmod = 10**9 + 7\n@lru_cache(maxsize=None)\ndef memoization(d, f, t):\n  if d == 0: \n    return int(t==0)\n  return sum(memoization(d-1, f, t-v) for v in range(1,f+1)) % mod", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        @lru_cache(maxsize=None)\n        def dp(d, t):\n            print((d,t))\n            if d == 0:\n                return 1 if t == 0 else 0\n            return sum(dp(d-1, t - x) for x in range(1, f+1))\n        return dp(d, target)%(10**9 + 7)\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mem = collections.defaultdict(int)\n        mem[0] = 1\n        for i in range(d):\n            curr = collections.defaultdict(int)\n            for face in range(1,f+1):\n                for val,count in list(mem.items()):\n                    newVal = face + val\n                    if newVal <= target:\n                        curr[newVal] += count \n            mem = curr\n        return mem[target]%(10**9+7)\n            \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0]*(target+1) for i in range(d+1)]\n        MOD = 1000000007\n        dp[0][0]=1\n        for dice in range(1,d+1):\n            for target in range(1,target+1):\n                if(target>dice*f):\n                    continue\n                else:\n                    face=1\n                    while(face<=f and face<=target):\n                        dp[dice][target]=(dp[dice][target]+dp[dice-1][target-face])%MOD\n                        face+=1\n        return dp[-1][-1]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        MOD = 10 ** 9 + 7\n        dp = [0] * (target + 1)\n        dp[0] = 1\n        for i in range(1, d + 1):\n            if target < i:\n                break\n            t = min(i * f, target)\n            dp[t] = sum(dp[t - j] for j in range(max(1, t - (i - 1) * f), min(f, t - i + 1) + 1)) % MOD\n            for t in reversed(range(i,  t)):\n                dp[t] = dp[t + 1] - dp[t] + (dp[t - f] if t - f >= i - 1 else 0) \n        return dp[target]", "class Solution:\n    def numRollsToTarget(self, d, f, target):\n        dp = [0] * (target+1)\n        dp[0] = 1\n        for i in range(d):\n            for j in range(target, -1, -1):\n                tot = 0\n                for k in range(1, 1 + min(f, j)):\n                    tot += dp[j-k]\n                dp[j] = tot\n        return dp[target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target > d*f:\n            return 0\n        if target == d * f:\n            return 1\n        if d==1 :\n            return 1\n        if f > target:\n            f = target\n        MOD = 10**9+7\n        dp = [[0 for j in range( d*f+1 +1) ]for i in range(d+1)]\n\n\n        for i in range(1,f+1):\n            dp[1][i] = 1\n        for i in range(d+1):\n            for j in range(d*f+1+1):\n                for t in range(1,f+1):\n                    if j-t>=i-1:\n                        dp[i][j] += dp[i-1][j-t]%MOD\n        return dp[d][target]%MOD", "class Solution:\n    @lru_cache(None)\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d == 0 or target <= 0:\n            return d == 0 and target == 0\n        res = 0\n        for i in range(1, f+1):\n            res = (res + self.numRollsToTarget(d - 1, f, target - i)) % (10**9 + 7)\n        return res\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def helper(rolls_left, t):\n            if not t and not rolls_left:\n                return 1\n            if not rolls_left or not t:\n                return 0\n            ret = 0\n            for v in range(1, min(f+1, t+1)):\n                if (rolls_left -1, t-v) not in memo:\n                    memo[(rolls_left -1, t-v)] = helper(rolls_left - 1, t-v)\n                ret += memo[(rolls_left -1, t-v)]\n            return ret\n        return helper(d,target) % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        @lru_cache(None)\n        def solve(s,t):\n            if s == 0:\n                if t == 0:return 1\n                return 0\n            ans = 0\n            for i in range(1,f+1):\n                if t >= i:\n                    ans += solve(s - 1,t - i)\n            return ans\n        \n        return solve(d,target) % (10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        modulo = 1000000007\n        memo = {}\n        def recurseRoll(d, target):\n            if d < 0:\n                return 0\n            if target < 0:\n                return 0\n            if target == 0 and d == 0:\n                return 1\n            s = 0\n            for i in range(1, f+1):\n                if ((d-1,target-i)) in memo:\n                    s+=memo[(d-1,target-i)]\n                else:\n                    s+=recurseRoll(d-1, target-i)\n            memo[(d, target)] = s\n            return s\n        return recurseRoll(d, target) % modulo", "from functools import lru_cache\nclass Solution:\n    @lru_cache\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp = [[0] * (target+1) for _ in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1, d+1):\n            for j in range(target+1):\n                if dp[i-1][j] > 0:\n                    for k in range(1, f+1):\n                        if j + k <= target:\n                            dp[i][j+k] += dp[i-1][j] \n                            dp[i][j+k] %= (10**9 + 7)\n        #print(dp)\n        return dp[d][target]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dpMatrix = [[0 for i in range(target+1)] for i in range(d)]\n        \n        for i in range(1,min(f+1, len(dpMatrix[0]))):\n            dpMatrix[0][i] = 1\n        \n        for i in range(1,len(dpMatrix)):\n            for j in range(1, len(dpMatrix[0])):\n                calcSum=0\n                for k in range(j-1, max(-1,j-f-1), -1):\n                    calcSum+= dpMatrix[i-1][k]\n                \n                dpMatrix[i][j] = calcSum\n        \n        return dpMatrix[-1][-1]%(10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def helper(d, target):\n            if d == 0:\n                 return 0 if target > 0 else 1\n            if (d, target) in memo:\n                return memo[(d,target)]\n            to_return = 0\n            for k in range(max(0, target-f), target):\n                to_return += helper(d-1, k)\n            memo[(d, target)] = to_return\n            return to_return\n        return helper(d, target) % (10**9 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mem = {(0, 0): 1}\n        def find(d: int, target: int):\n            if (d, target) in mem:\n                return mem[(d, target)]\n            \n            if d == 0:\n                return 0\n            \n            res = 0\n            d -= 1\n            for i in range(1, min(target - d, f)+1):\n                res += find(d, target-i)\n            mem[(d+1, target)] = res\n            return res\n        \n        return find(d, target) % (10**9 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        def solve(s,t):\n            if s == 0:\n                if t == 0:return 1\n                return 0\n            if dp[s][t] != -1:return dp[s][t]\n            ans = 0\n            for i in range(1,f+1):\n                if t >= i:\n                    ans += solve(s - 1,t - i)\n            dp[s][t] = ans\n            return dp[s][t]\n        dp = [[-1]*(target+1) for _ in range(d+1)]\n        return solve(d,target) % (10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp_map ={}\n        \n        for i in range(target):\n            dp_map[(1,i+1)] = 0\n        for i in range(f):\n            dp_map[(1,i+1)] = 1\n        \n        def recurse_with_mem(d,target):\n            \n            if (d,target) in dp_map:\n                return dp_map[(d,target)]\n\n            if target<=0:\n                return 0\n            \n            num_ways = 0\n            for i in range(f):\n                num_ways += recurse_with_mem(d-1,target-i-1)\n        \n            dp_map[(d,target)] = num_ways\n            return num_ways\n        \n        return recurse_with_mem(d,target)%(10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def dp(d,target):\n            if d == 0:\n                return 0 if target>0 else 1\n            if (d,target) in memo:\n                return memo[(d,target)]\n            res = 0\n            for k in range(max(0, target-f),target):\n                res += dp(d-1, k)\n            memo[(d,target)] = res\n            return res\n                \n        return dp(d,target) % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def dp(d, target):\n            nonlocal memo, f\n            if d == 0:\n                return 1 if target == 0 else 0\n            if (d, target) in memo:\n                return memo[(d, target)]\n            res = 0\n            for i in range(max(0, target-f), target):\n                res += dp(d-1, i)\n            memo[(d, target)] = res\n            return res\n        return dp(d, target)%(10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def helper(dice, tar):\n            if dice == 0:\n                return 1 if tar == 0 else 0\n            \n            if (dice, tar) in memo:\n                return memo[(dice, tar)]\n            \n            res = 0\n            for k in range(max(0, tar-f), tar):\n                res += helper(dice-1, k)\n            \n            memo[(dice, tar)] = res\n            return res\n        \n        \n        return  helper(d, target) % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        \n        def helper(dice, t):\n            if dice == 0:\n                return 1 if t == 0 else 0\n            \n            if (dice, t) in memo:\n                return memo[(dice, t)]\n            \n            res = 0\n            for k in range(max(0, t-f), t):\n                res += helper(dice-1, k)\n            \n            memo[(dice, t)] = res\n            return res\n        \n        return helper(d, target) %(10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def dp(d,target):\n            if d == 0:\n                return 1 if target == 0 else 0\n            if (d,target) in memo:\n                return memo[(d,target)]\n            result = 0\n            for k in range(max(0,target-f), target):\n                result += dp(d-1,k)\n            memo[(d,target)] = result\n            return memo[(d,target)]\n        return dp(d, target) % (10**9 + 7)", "class Solution:\n    # Recursive memoized solution\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def num_rolls_util(level, target):\n            if level == 0:\n                return target == 0\n\n            if (level, target) in memo:\n                return memo[(level, target)]\n            else:\n                res = 0\n                for i in range(max(0, target - f), target):\n                    res += num_rolls_util(level - 1, i)\n\n                memo[(level, target)] = res\n\n                return res % (10 ** 9 + 7)\n        \n        return num_rolls_util(d, target)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d>target or d*f<target: return 0\n        \n        if f>target: f = target\n        \n        memo = [[0 for _ in range(target)] for _ in range(d)]\n        \n        # set first line\n        for i in range(f):\n            memo[0][i] = 1\n        \n        # run algo\n        for i,row in enumerate(memo[1:]):\n            for j,_2 in enumerate(row):\n                if j-f<0:\n                    memo[i+1][j] = sum(memo[i][0:j]) % 1000000007\n                else:\n                    memo[i+1][j] = sum(memo[i][j-f:j]) % 1000000007\n                \n        return memo[-1][-1] % 1000000007", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        self.mapx = {}\n        return self.rec(d, f, target)\n       \n    def rec(self, d, f, target):\n        if d == 0:\n            if target == 0:\n                return 1\n            return 0\n        \n        count = 0\n        \n        for num in range(1,f+1):\n            if target-num >= 0:\n                nextState = (d-1, target-num)\n                if nextState not in self.mapx:\n                    count += self.rec(d-1, f, target-num)\n                else:\n                    count += self.mapx.get(nextState,0)\n                    \n        count = count % 1000000007\n        self.mapx[(d, target)] = count \n        return count", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n\n        cache = {}\n        \n        def helper(d, target):\n            if d == 0 and target == 0:\n                return 1\n            if d == 0:\n                return 0\n            if (d, target) in cache:\n                return cache[(d, target)]\n            \n            result = 0\n            for i in range(max(0, target-f), target):\n                result += helper(d-1, i)\n                \n            cache[(d, target)] = result\n            return result\n    \n        \n        return helper(d, target) % ((10**9)+7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        self.dic = {}\n        self.f = f\n        return self.dfs(d, target) % (10**9 + 7)\n        \n        \n    def dfs(self, dices, tar):\n        if (dices, tar) in self.dic:\n            return self.dic[(dices, tar)]\n        elif tar < 0:\n            return 0\n        elif dices == 1 and tar <= self.f:\n            return 1\n        elif dices == 1:\n            return 0\n        else:\n            r = 0\n            for i in range(1, min(self.f+1, tar)):\n                r += self.dfs(dices-1, tar-i)\n            \n            self.dic[(dices, tar)] = r\n            return r\n", "class Solution:\n    def numRollsToTarget(self, k: int, f: int, target: int) -> int:\n        d = {}\n        def h(x,t):\n            v = (x,t)\n            if v in d:\n                return d[v]\n            if x == 0 and t == 0:\n                return 1\n            if x == 0 or t == 0:\n                return 0\n            s = 0\n            for i in range(1,f+1):\n                s+=h(x-1,t-i)\n            d[v] = s\n            return s\n        x = h(k,target)\n        return x%(10**9+7)", "class Solution:\n    def numRollsToTarget(self, d, f, target):\n        dp = [1] + [0]*target\n        for i in range(d):\n            for j in range(target, -1, -1):\n                dp[j] = sum([dp[j-k] for k in range(1, 1+min(f, j))] or [0])\n        return dp[target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        D = {}\n        def func(d,f, target):\n            res = 0\n            if d==0 and target==0:\n                return 1\n            if d==0 and target!=0:\n                return 0\n            if target<0:\n                return 0\n            \n            for i in range(1,f+1):\n                if (d-1,target-i) not in D:\n                    D[d-1,target-i] = func(d-1,f,target-i)\n                res+=D[d-1,target-i]\n                res = res%(10**9 + 7)\n            return res\n        \n        #d=2\n        #f=6\n        #target=7\n        return func(d,f,target)\n            \n", "class Solution:\n    def numRollsToTarget(self, d, f, target):\n        dp = [0] * (target+1)\n        dp[0] = 1\n        for i in range(d):\n            for j in range(target, -1, -1):\n                dp[j] = sum([dp[j-k] for k in range(1, 1+min(f, j))] or [0])\n        return dp[target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # bottom up DP\n        prev_dp = [0] * (target + 1)\n        prev_dp[0] = 1\n        for num_dice in range(1, d + 1):\n            curr_dp = [0] * (target + 1)\n            for face in range(1, f+1):\n                for total in range(face, target + 1):\n                    curr_dp[total] = (curr_dp[total] + prev_dp[total - face]) % (10 ** 9 + 7)\n            prev_dp = curr_dp\n        return prev_dp[-1]", "class Solution:\n    # @lru_cache(maxsize=None)\n    # def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n#         mod = 1e9 + 7\n#         if target < 0 or d < 0:\n#             return 0\n\n#         if target == 0 and d == 0:\n#             return 1\n\n#         ways = 0\n#         for dice in range(1, 1 + f):\n#             ways += self.numRollsToTarget(d - 1, f, target - dice\n#             )\n#         return int(ways % mod)\n    \n#         dp = [0] * (1 + target)\n#         dp[0] = 1\n#         mod = 1e9 + 7\n\n#         for rep in range(d):\n#             newDP = [0] * (1 + target)\n#             for i in range(1, 1 + f):\n#                 for j in range(1, 1 + target):\n#                     if i <= j:\n#                         newDP[j] += dp[j - i]\n#                         newDP[j] %= mod\n#             dp = newDP\n#         return int(dp[-1])\n\n    # @lru_cache(maxsize=None)\n    def numRollsToTarget(self, d, f, target, result=0):\n#         MOD = 7 + 1e9\n#         if d == 0:\n#             return target == 0\n\n#         for i in range(1, f + 1):\n#             result = (result + self.numRollsToTarget(d - 1, f, target - i)) % MOD\n\n#         return int(result)\n        \n        MOD = 7 + 1e9\n        dp = [0] * (1 + target)\n        dp[0] = 1\n        for i in range(1, 1 + d):\n            newDP = [0] * (1 + target)\n            prev = dp[0]\n            for j in range(1, 1 + target):\n                newDP[j] = prev\n                prev = (prev + dp[j]) % MOD\n                if j >= f:\n                    prev = (prev - dp[j - f] + MOD) % MOD\n            dp = newDP\n        return int(dp[-1])", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        # we can use memoization\n        DP = {}\n        def get_rolls(n, t):\n            if n == 1:\n                if 0 < t <= f:\n                    return 1\n                return 0\n            if (n, t) in DP:\n                return DP[(n, t)]\n            \n            total = 0\n            \n            for i in range(1, f+1):\n                total += get_rolls(n-1, t-i)\n            \n            DP[(n, t)] = total\n            return total\n        \n        return get_rolls(d, target) % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp1 = [0]*(target + 1)\n        dp2 = [0]*(target + 1)\n        dp1[0] = 1\n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                for k in range(1, min(j, f) + 1):\n                    dp2[j] =  dp2[j] + dp1[j-k]\n            dp1 = dp2\n            dp2 = [0]*(target + 1)\n                    \n        return dp1[target] % (10**9 + 7)\n", "class Solution:\n    def __init__(self):\n        self.dp = []\n        \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # Initiate memoization array\n        for dice in range(0, d + 1):\n            self.dp.append([-1] * (target + 1))\n        \n        return self.rollDice(d, f, target) % (10 ** 9 + 7)\n    \n    def rollDice(self, d: int, f: int, target: int) -> int:\n        if self.dp[d][target] != -1:\n            return self.dp[d][target]\n        \n        if d == 1:\n            if f >= target:\n                return 1\n            else:\n                return 0\n        \n        self.dp[d][target] = 0\n        for nextRoll in range(1, f + 1):\n            if target - nextRoll > 0:\n                self.dp[d][target] += self.rollDice(d - 1, f, target - nextRoll)\n        \n        return self.dp[d][target]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        def find_next(dice_left, current_val):\n            if current_val > target:\n                return 0\n            if dice_left == 0:\n                if current_val == target:\n                    return 1\n                return 0\n            \n            if (dice_left, current_val) not in seen:\n                combinations = 0\n                for i in range(1, f + 1):\n                    combinations += find_next(dice_left - 1, current_val + i)\n                seen[(dice_left, current_val)] = combinations % 1000000007\n                \n            return seen[(dice_left, current_val)]\n        \n        seen = {}\n        return find_next(d, 0) \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        bottomWidth = f + ((d-1)*(f-1))\n        currentLayer = [0 for i in range(bottomWidth)] + [1 for i in range(f)] + [0 for i in range(bottomWidth)]\n        nextLayer = []\n        \n        for run in range(d-1): # runs as many times as we traverse down the triangle\n            # update each next layer number to be sum of f numbers above it\n            for i in range(f, len(currentLayer)-f):\n                localSum = 0\n                for j in range(i, f+i):\n                    localSum += currentLayer[j]\n                nextLayer += [localSum]\n                \n            neededZeros = [0 for i in range((len(currentLayer) - len(nextLayer))//2)]\n            currentLayer = neededZeros + nextLayer + neededZeros\n            nextLayer = []\n            \n        # at this point, shave off the zeros\n        while 0 in currentLayer:\n            currentLayer.remove(0)\n            \n        # at this point, the answer must be less than or equal to d, and greater than or equal to f*d.\n        if target-d >= len(currentLayer): \n            return 0\n        else: \n            return currentLayer[target-d] % ((10**9) + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # bottom up DP\n        prev_dp = [0] * (target + 1)\n        prev_dp[0] = 1\n        for num_dice in range(1, d + 1):\n            curr_dp = [0] * (target + 1)\n            for face in range(1, f+1):\n                for total in range(face, target + 1):\n                    curr_dp[total] = (curr_dp[total] + prev_dp[total - face]) % (10 ** 9 + 7)\n            prev_dp = curr_dp\n            print(prev_dp)\n        return prev_dp[-1]", "class Solution:\n    def numRolls(self, d, f, target, memo):\n        if target < d:\n            # print(f\\\"d {d} f {f} target {target} ans {0}\\\")\n            return 0\n        if d == 1:\n            # print(f\\\"d {d} f {f} target {target} ans {int(target <= f)}\\\")\n            return int(target <= f)\n        \n        if (d, f, target) in memo:\n            return memo[(d, f, target)]\n\n        total = 0\n        for new_target in range(target - f, target):\n            total += self.numRolls(d - 1, f, new_target, memo)\n            total = total % (10**9 + 7)\n        # print(f\\\"d {d} f {f} target {target} ans {total}\\\")\n        memo[(d, f, target)] = total\n        return total\n\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        ans = self.numRolls(d, f, target, memo)\n        # print(memo)\n        return ans\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        memo = defaultdict(int)\n\n        def solve(d, f, target):\n            if (d,f,target) in memo:\n                return memo[(d,f,target)]\n            if d==0:\n                if target!=0:\n                    return 0\n                else:\n                    return 1\n            dp = 0\n            for i in range(1,f+1):\n                dp += solve(d-1,f,target-i)\n            memo[(d,f,target)] = dp\n            return dp\n        \n        return solve(d,f,target)%(10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [1 if i < f else 0 for i in range(target)]\n        for n in range(2, d+1):\n            new_dp = [0 for _ in range(target)]\n            cumsum = 0\n            for i in range(target-1):\n                cumsum += dp[i]\n                if i >= f:\n                    cumsum -= dp[i-f]\n                new_dp[i+1] = cumsum \n            dp = new_dp\n            # print(n, dp)\n        return dp[-1] % (10**9 + 7)", "\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        def helper(h, d, target):\n            # if target is too small or if it is out of range\n            if not d and not target:\n                return 1\n\n            if (d, target) in h:\n                return h[(d, target)]        # directly access from hash table\n            res = 0\n            for i in range(1, f + 1):\n                if target - i >= 0 and d > 0:\n                    res += helper(h, d - 1, target - i)       # check all possible combinations\n            h[(d, target)] = res\n            return h[(d, target)]\n        \n        h = {}\n        return helper(h, d, target) % (10 ** 9 + 7)", "class Solution:\n    def helper(self,d,f,target):\n        if(d == 0):\n            if(target == 0):\n                return 1\n            else:\n                return 0\n        \n        if((d,target) in self.memo):\n            return self.memo[(d,target)]\n        \n        count = 0\n        for i in reversed(list(range(1,min(target+1,f+1)))):\n            count+=self.helper(d-1,f,target-i)\n        \n        self.memo[(d,target)]=count\n        return count\n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        self.memo = dict()\n        return self.helper(d,f,target)%(10**9 +7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        return self.recurse(d,0,f,0,target,{})%(10**9+7)\n    \n    def recurse(self,dices,dno,faces,cursum,target,cache):\n        if cursum>target:\n            return 0\n        \n        if dno==dices:\n            if cursum==target:\n                return 1\n            return 0\n        \n        if (dno,cursum) in cache:\n            return cache[(dno,cursum)]\n        \n        ways=0\n        for curface in range(1,faces+1):\n            ways+=self.recurse(dices,dno+1,faces,cursum+curface,target,cache)\n        cache[(dno,cursum)]=ways\n        return ways", "class Solution:\n    # Recursive memoized solution\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        return self.num_rolls_util(memo, d, f, target, 0, 0)\n    \n    \n    def num_rolls_util(self, memo, d, f, target, level, cur_sum):\n        if level == d:\n            return cur_sum == target\n        \n        if (level, cur_sum) in memo:\n            return memo[(level, cur_sum)]\n        \n        res = 0\n        for i in range(1, f + 1):\n            if cur_sum + i <= target:\n                res += self.num_rolls_util(memo, d, f, target, level + 1, cur_sum + i)\n            \n        memo[(level, cur_sum)] = res\n        \n        return res % (10 ** 9 + 7)", "class Solution:\n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        #[1,2,3,4,5,6], target=7\n        #[1,2,3,4,5,6]\n        #[1,2,3,4,5,6]\n        #[]\n        \n        store = {}\n        \n        def helper(d, f, target):\n            if d==0 or f==0 or target<=0:\n                return 0\n            if d==1 and target>f:\n                return 0\n            if d==1 and target<=f:\n                return 1\n        \n            if (d, f, target) in store:\n                 return store[(d,f,target)]\n        \n            n = 0\n            for i in range(1, f+1):\n                n += helper(d-1, f, target-i)\n        \n            store[(d, f, target)] = n\n            return n\n    \n        #d=2, f=6, t=7\n        #i=1, 1,6,6\n        \n        return (helper(d, f, target))%(10**9 + 7)\n            \n        #2,6,7\n        #(1,6,6), (1,6,5), (1,6,4), (1,6,3), (1,6,2),(1,6,1)\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        \n        def dfs(n, t):\n            if n == 0:\n                return t == 0\n            if (n, t) in memo:\n                return memo[n, t]\n            \n            ret = 0\n            for face in range(1, f+1):\n                ret += dfs(n-1, t-face)\n            \n            memo[n, t] = ret % (10**9 + 7)\n            return memo[n, t]\n        \n        return dfs(d, target)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        def backtrack(index=d-1,target=target,dp={}):\n            if index==-1 and target==0:return 0\n            if index<0 or target<=0:return None\n            if (index,target) in dp:return dp[(index,target)]\n            if target>f:start=f\n            else:start=target\n            count=0\n            for i in range(start,0,-1):\n                res=backtrack(index-1,target-i,dp)\n                if res!=None:\n                    count+=res if res else 1\n            dp[(index,target)]=count if count else None\n            return dp[(index,target)]\n        count=backtrack()\n        return (count%(10**9+7)) if count!=None else 0\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def helper(d, target):\n            if d == 0 and target == 0:\n                return 1\n            if d == 0:\n                return 0\n            if (target, d) in memo:\n                return memo[(target, d)]\n            num_ways = 0\n            for i in range(1, f+1):\n                if target - i >= 0:\n                    num_ways += helper(d-1, target-i)\n            memo[(target, d)] = num_ways\n            return num_ways\n        \n        return helper(d, target) % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [0] * (target+1)\n        dp[0] = 1\n        for i in range(1, d+1):\n            temp = [0] * (target+1)\n            # iterate each tot from 1 to target\n            for j in range(1, target+1):\n                # k is each face \n                temp[j] = sum(dp[j-k] if k <= j else 0 for k in range(1, f+1))\n            dp = temp\n        return dp[target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        if target > 900:\n            return 0\n        memo = {}\n        \n        def dfs(dice, t):\n            if dice == 0 and t == 0:\n                return 1\n            if dice == 0 or t == 0:\n                return 0\n            \n            if (dice, t) in memo:\n                return memo[(dice, t)]\n            count = 0\n            for n in range(1, f+1):\n                count += dfs(dice-1, t-n)\n            memo[(dice, t)] = count % ((10 ** 9) + 7)\n            return memo[(dice, t)]\n        \n        return dfs(d, target)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        modulo = 10**9 + 7\n        dp = [[0 for i in range(target+1)] for j in range(d+1)]\n        \n        for dd in range(1, d+1):\n            for tt in range(dd, min(f * dd, target) + 1 ):\n                if dd == 1:\n                    dp[dd][tt] = 1\n                else:\n                    end   = tt - 1\n                    start = max(1, tt - f)\n                    dp[dd][tt] = sum(dp[dd-1][start:end+1])\n    \n        return dp[d][target] % modulo   ", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        return self.num_rolls_util(memo, d, f, target, 0, 0)\n    \n    \n    def num_rolls_util(self, memo, d, f, target, level, cur_sum):\n        if level == d:\n            return cur_sum == target\n        \n        if (level, cur_sum) in memo:\n            return memo[(level, cur_sum)]\n        \n        res = 0\n        for i in range(1, f + 1):\n            res += self.num_rolls_util(memo, d, f, target, level + 1, cur_sum + i)\n            \n        memo[(level, cur_sum)] = res\n        \n        return res % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        self.dp = {}\n        \n        def recur_top_down(d, f, target):\n            \n            if d == 0 or target <= 0: \n                return d == 0 and target == 0\n\n            if (d, target) in self.dp: return self.dp[(d, target)]\n            \n            res = 0\n            for i in range(f):\n                res += recur_top_down(d-1, f, target-(i+1)) % (10**9+7)\n\n            res = res % (10**9+7)\n            self.dp[(d, target)] = res \n            \n            return res \n            \n        \n        return recur_top_down(d, f, target)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mem = {}\n        def dfs(l, target):\n            if((l, target) in mem):\n                return mem[(l, target)]\n            if(l==d):\n                return int(target==0)\n            MOD = 1e9+7\n            ans=0\n            for i in range(1, f+1):\n                ans = (ans+dfs(l+1, target-i))%MOD\n            mem[(l, target)] = ans\n            return ans\n        return int(dfs(0, target))", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        self.dp = {}\n        \n        def recur_top_down(d, f, target):\n            \n            if d == 0 : \n                return 1 if target == 0 else 0\n\n            if (d, target) in self.dp: return self.dp[(d, target)]\n            \n            res = 0\n            for i in range(f):\n                res += recur_top_down(d-1, f, target-(i+1)) % (10**9+7)\n\n            res = res % (10**9+7)\n            self.dp[(d, target)] = res \n            \n            return res \n            \n        \n        return recur_top_down(d, f, target)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        def count_for_roll(num_dice, curr_target):\n            \n            if num_dice == 0 and curr_target == 0:\n                return 1\n            \n            if num_dice == 0 or curr_target == 0:\n                return 0\n            \n            if (num_dice, curr_target) in memo:\n                return memo[(num_dice, curr_target)]\n            \n            curr_count = 0\n            \n            for face in range(1, f+1):\n                \n                new_target = curr_target - face\n                \n                if new_target < 0:\n                    break\n                    \n                curr_count += count_for_roll(num_dice - 1, new_target)\n            \n            memo[(num_dice, curr_target)] = curr_count\n            return curr_count % mod\n        \n        memo = {}\n        mod = 10**9 + 7\n        \n        return count_for_roll(d, target)\n\n'''\nd = 2, f = 6, t = 7\n\n1\n    1\n    2\n    3\n    4\n    5\n    6 -> inc\n    \n2\n    1\n    2\n    3\n    4\n    5 -> inc\n    6 -> stop?\n    \n3 \n    1\n    2\n    3\n    4 -> inc\n    5 -> stop\n    \n    \n\n'''", "class Solution:\n    def helper(self,d,f,target,cursum,dp):\n        if(d==0):\n            if(target==cursum):\n                return 1\n            else:\n                return 0\n        if(cursum>target):\n            return 0\n        cnt = 0\n        if((d,cursum) in dp):\n            return dp[(d,cursum)]\n        for i in range(1,f+1):\n            cnt+=self.helper(d-1,f,target,cursum+i,dp)\n        dp[(d,cursum)]=cnt%(pow(10,9)+7)\n        return cnt%(pow(10,9)+7)\n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp={}\n        return self.helper(d,f,target,0,dp)", "class Solution:\n    # Recursive memoized solution\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        return self.num_rolls_util(memo, d, f, target, 0, 0)\n    \n    \n    def num_rolls_util(self, memo, d, f, target, level, cur_sum):\n        if level == d:\n            return cur_sum == target\n        \n        if (level, cur_sum) in memo:\n            return memo[(level, cur_sum)]\n        \n        res = 0\n        for i in range(1, f + 1):\n            res += self.num_rolls_util(memo, d, f, target, level + 1, cur_sum + i)\n            \n        memo[(level, cur_sum)] = res\n        \n        return res % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def helper(d, target):\n            if d==0 and target == 0:\n                return 1\n            if d==0 or target == 0:\n                return 0\n            if (d,target) in memo:\n                return memo[(d,target)]\n            else:\n                ans = 0\n                for i in range(1, f+1):\n                    ans+= helper(d-1, target-i)\n                memo[(d,target)] = ans%(10**9+7)\n                return memo[(d,target)]\n        return helper(d, target)", "from collections import defaultdict\n\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = defaultdict(int)\n        \n        def helper(d, target):\n            if d == 0:\n                return 1 if target == 0 else 0\n            if (d, target) in memo:\n                return memo[(d, target)]\n\n\n            #for c in range(1, f + 1):\n            for c in range(max(0, target-f), target):\n                #memo[(d, target)] += helper(d - 1, target - c, memo)\n                memo[(d, target)] += helper(d - 1, c)   \n            return memo[(d, target)]\n        return helper(d, target) % (10**9 + 7)\n    \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # f(n) = f(n - 1) + f(n-2) + ...\n        dp = [[0 for i in range(target+1)] for t in range(d+1)]\n        for dd in range(1, d+1):\n            for tt in range(dd, min(f*dd, target)+1):\n                if dd == 1:\n                    dp[dd][tt] = 1\n                else:\n                    end = tt -1\n                    start = max(1, tt-f)\n                    dp[dd][tt] = sum(dp[dd-1][start:end+1])\n        return dp[d][target]%(10**9 + 7)\n        \n    \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        cache = {}\n        def helper(d,target):\n            # print(d,target)\n            if target == 0 and d == 0:\n                return 1\n            if d == 0:\n                return 0\n            if (d,target)  in cache:\n                return cache[(d,target)]\n            ways = 0\n            for i in range(1,f+1):\n                if target - i >= 0:\n                    ways = (ways + helper(d-1,target-i)) % 1000000007\n            cache[(d,target)] = ways\n            return cache[(d,target)]\n        \n        return helper(d,target)\n", "class Solution:\n    '''\n    similar to coin Change problem.\n        \n    '''\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp1 = [0 for _ in range(target+1)]\n        dp2 = dp1[:]\n        dp1[0] = 1\n        mod = 10 ** 9 + 7\n        for i in range(1, d+1):\n            for j in range(target+1):\n                for k in range(1, min(j,f) + 1):\n                    dp2[j] = (dp2[j] + dp1[j-k]) % mod\n            dp1 = dp2\n            dp2 = [0 for _ in range(target+1)]\n        return dp1[target] % mod\n    \n# https://www.youtube.com/watch?time_continue=872&v=UiYVToWORMY&feature=emb_logo\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        MOD = pow(10, 9) + 7\n        def dfs(d_left=d, target_left=target):\n            if (d_left, target_left) in memo:\n                return memo[(d_left, target_left)]\n            if not d_left:\n                return 1 if not target_left else 0\n            else:\n                memo[(d_left, target_left)] = 0\n                for face in range(1, min(f+1, target_left+1)):\n                    memo[(d_left, target_left)] += dfs(d_left-1, target_left-face)\n                return memo[(d_left, target_left)]\n        return dfs() % MOD", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        BASE = 10**9 + 7\n        \n        memo = {(0,0): 1}\n        def dfs(num, tar):\n            \n            nonlocal BASE\n            \n            if (num, tar) in memo:\n                return memo[(num, tar)]\n            \n            if num == 0 or tar == 0:\n                return -1\n            \n            cnt = 0\n            for i in range(1, f+1):\n                sub = dfs(num - 1, tar-i)\n                if sub != -1: cnt += sub\n            memo[(num, tar)] = cnt % BASE\n            \n            return memo[(num, tar)]\n    \n        dfs(d, target)\n        #print(memo)\n        return memo[(d, target)]", "# from (D * F * target) -> O(D * target)\nclass Solution:\n    def numRollsToTarget(self, D: int, F: int, target: int) -> int:\n        # dp[d][t] -> how many ways to form t using d dices\n        dp = [[0] * (target + 1) for _ in range(2)]\n        dp[0][0] = 1\n        for d in range(1, D + 1):\n            cd = d & 0x1\n            pd = (d - 1) & 0x1\n            dp[cd][0] = 0\n            for t in range(1, target + 1):\n                dp[cd][t] = (dp[cd][t - 1] + dp[pd][t - 1] - (dp[pd][t - F - 1] if t - F - 1 >= 0 else 0)) % 1000000007\n        return dp[D & 0x1][target]\n    \n    def numRollsToTarget(self, D: int, F: int, target: int) -> int:\n        dp = [0] * (target + 1)\n        dp[0] = 1\n        for d in range(1, D + 1):\n            ndp = [0] * (target + 1)\n            for i in range(1, target + 1):    \n                ndp[i] = sum(dp[i - f] for f in range(1, F + 1) if i - f >= 0) % 1000000007\n            dp = ndp\n        return dp[-1]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        self.map = collections.defaultdict(int)\n        return self.noOfWays(d,f, target)\n        \n    def noOfWays(self,d, f, target):\n           \n        if(d==0 and target==0):\n            return 1\n        elif(d==0):\n            return 0\n\n        if((d,target) in self.map):\n            return self.map[(d,target)]\n        res = 0\n        for i in range(1, f+1):\n            res+= (self.noOfWays(d-1,f, target-i))\n        self.map[(d,target)] = res  \n        return res%(10**9 + 7)\n", "MOD = 10 ** 9 + 7\n\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        ways = [0] + [1] * min(f, target) + [0] * max(target - f, 0)\n        for _ in range(d - 1):\n            for i in reversed(range(1, target + 1)):\n                ways[i] = 0\n                for j in range(1, min(i, f + 1)):\n                    ways[i] = (ways[i] + ways[i - j]) % MOD\n        return ways[target]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        mod = int(math.pow(10,9)+7)\n        def recur(d,target):\n            if (d,target) in memo:\n                return memo[(d,target)]\n            if d<0 or target<0:\n                return 0\n            if d == 0 and target == 0:\n                return 1\n            ways = 0\n            for i in range(1,f+1):\n                if target-i < 0:\n                    break\n                ways = int(ways + recur(d-1,target-i))%mod\n            memo[(d,target)] = ways\n            return ways\n        return recur(d,target)\n", "class Solution:\n    @lru_cache(None)\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # dp[i][k]: the number of ways to get target \\\"k\\\" using \\\"i\\\" dices\n        # dp[0][0] = 1\n        # dp[i][k] = dp[i-1][k] + sum(dp[i-1][k - ff] for ff in range(1, f + 1))\n        dp = [1] + [0] * target\n        mod = 10**9 + 7\n        for _ in range(d):\n            for i in range(target, -1, -1):\n                dp[i] = sum(dp[i-ff] for ff in range(1, f + 1) if i >= ff) % mod\n        return dp[-1] % mod\n        # for i in range(1, d + 1):\n        #     for j in range(1, target + 1):\n                # dp[i]\n        \n        dp = [[0] * (target + 1) for _ in range(d + 1)]\n        mod = 10 ** 9 + 7\n        dp[0][0] = 1\n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                # if i == 0 and j == 0:\n                #     dp[i][j] = 1\n                # elif j == 0:\n                #     dp[i][j] = 1\n                # elif i == 0:\n                #     continue\n                # else:\n                dp[i][j] = (sum(dp[i-1][j-ff] for ff in range(1, f + 1) if j >= ff))\n        return dp[-1][-1] % mod\n        \n        \n        # if d == 0 or target <= 0:\n        #     return d == 0 and target == 0\n        # res = 0\n        # for i in range(1, f+1):\n        #     res = (res + self.numRollsToTarget(d - 1, f, target - i)) % (10**9 + 7)\n        # return res\n", "class Solution:\n    def __init__(self):\n        self.memo = {}\n        \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        res = 0\n        if (d, target) in self.memo:\n            return self.memo[(d, target)]\n        for i in range(1, f + 1):\n            if target - i == 0 and d == 1:\n                res += 1\n            elif target - i > 0 and d > 1:\n                res += self.numRollsToTarget(d - 1, f, target - i)\n        self.memo[(d, target)] = res\n        return res % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        \n        for dd in range(1, d+1):\n            for tt in range(dd, min(f*dd, target)+1):\n                if dd == 1:\n                    dp[dd][tt] = 1\n                else:\n                    dp[dd][tt] = sum(dp[dd-1][max(1, tt-f):tt])\n                    \n        return dp[d][target] % (10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        self.cache = {}    \n        return self.helper(0, 0, d, f, target) % (10**9 + 7)\n    \n    def helper(self, currD, currSum, d, f, target):\n        if currD == d:\n            return currSum == target\n        \n        if currD in self.cache and currSum in self.cache[currD]:\n            return self.cache[currD][currSum]\n        \n        ways = 0\n        for i in range(1, f+1):\n            ways += self.helper(currD+1, currSum + i, d, f, target)\n        \n        if currD not in self.cache:\n            self.cache[currD] = {}\n        self.cache[currD][currSum] = ways\n        return ways", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp = [[0] * (target+1) for _ in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                dp[i][j] = sum(dp[i-1][j-k] for k in range(1, min(f,j)+1) )            \n        return dp[-1][-1] % (10**9 + 7)\n    \n#         if target > d*f:\n#             return 0\n#         dicti = collections.defaultdict(int)\n#         def dice_target(rem_dice, summ):\n#             if rem_dice == 0:\n#                 return 1 if summ == target else 0\n#             if summ > target:\n#                 return 0\n#             if (rem_dice, summ) in dicti:\n#                 return dicti[rem_dice, summ]\n\n#             for i in range(1, f+1):\n#                 dicti[rem_dice, summ] += dice_target(rem_dice-1, summ+i)\n#             return dicti[rem_dice, summ]\n        \n        \n#         return dice_target(d, 0) % (10**9 + 7)\n\n", "from math import comb\n\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dic = {}\n        return self.helper(d,f,target,dic)\n    \n    def helper(self, d2, f2, target2,dic):\n        if target2 == 0 and d2 == 0:\n            return 1\n        if (d2,f2,target2) in dic:\n            return dic[(d2,f2,target2)]\n        if target2 < d2 or d2*f2 < target2:\n            dic[(d2,f2,target2)] = 0\n            return 0\n        elif d2 == 1:\n            dic[(d2,f2,target2)] = 1\n            return 1\n        tot = 0\n        for i in range(0,d2+1):\n            num_poss = self.helper(d2-i,f2-1,target2 - i * f2,dic) * comb(d2,i)\n            tot += num_poss % (10**9 + 7)\n        dic[(d2,f2,target2)] = tot % (10**9 + 7)\n        return tot % (10**9 + 7)\n                \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for x in range(d + 1)]for y in range(target + 1)]\n        for i in range(1, min(f + 1, target + 1)):\n            dp[i][1] = 1\n        for i in range(1, target + 1):\n            for j in range(2, d + 1):\n                val = 0\n                for k in range(1, f + 1):\n                    if i - k >= 0:\n                        val += dp[i - k][j - 1]\n                dp[i][j] = val\n        return dp[target][d]%(10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        #dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        dp = [0 for _ in range(target+1)]\n        dp[0] = 1\n        #dp[0][0] = 1\n        \n        for i in range(1, d+1):\n            new = [0]\n            for j in range(1, target+1):\n                new.append(0)\n                for k in range(1, f+1):\n                    if j-k>=0:\n                        new[-1]+=dp[j-k]\n                        #dp[i][j]+=dp[i-1][j-k]\n            dp = new             \n        return dp[-1]%(10**9+7)  \n        return dp[-1][-1]%(10**9+7)\n                \n                \n    \n    '''\n    f = 6\n    \n     01234567\n    010000000\n    101111110\n    200123456\n         \n         \n         \n    '''", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0]*(target+1) for i in range(d+1)]\n        for i in range(1,d+1):\n            for j in range(1,target+1):\n                if i ==1:\n                    if j<=f:\n                        dp[i][j]=1\n                else:\n                    if j>=i:\n                        for k in range(1,min(j+1,f+1)):\n                            dp[i][j] += dp[i-1][j-k]\n        \n        return (dp[-1][-1]%((10**9)+7))", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for x in range(target+1)] for y in range(d+1)]\n        dp[0][0] = 1\n        \n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                total_sum = 0\n                for k in range(1, f+1):\n                    if j-k >= 0:\n                        total_sum += dp[i-1][j-k]\n                dp[i][j] = total_sum\n        return dp[d][target] % (10**9 + 7)\n            \n        \n        \n        \n        \n        # memo = {}\n        # def dp(d, target):\n        #     if d == 0:\n        #         return 0 if target > 0 else 1\n        #     if (d, target) in memo:\n        #         return memo[(d, target)]\n        #     to_return = 0\n        #     for k in range(max(0, target-f), target):\n        #         to_return += dp(d-1, k)\n        #     memo[(d, target)] = to_return\n        #     return to_return\n        # return dp(d, target) % (10**9 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for j in range(target+1)] for i in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                dp[i][j] = sum([dp[i-1][j-k] for k in range(1, 1+min(f, j))])\n        return dp[d][target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(target+1)]]\n        #dp.append([0 for _ in range(target+1)])\n        for i in range(1,min(f+1,target+1)):\n            dp[0][i] = 1 \n        for i in range(2,d+1):\n            dp.append([0 for _ in range(target+1)])\n            for t in range(i,target+1):\n                for d in range(1,min(t,f+1,target+1)):\n                    if t - d >= 0 and dp[-2][t-d]:\n                        dp[-1][t] += dp[-2][t - d]\n                    else:\n                        #print('')\n                        0\n            dp.pop(0)\n        for row in dp:\n            #print(row)\n            0\n        return (dp[0][-1]) % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = [0]*(target+1)\n        memo[0] = 1\n        maxV = 10**9+7\n        for _ in range(d):\n            for tv in range(target,-1,-1):\n                memo[tv] = 0 #since have must use all dices! So reaching tv with less than d dices doesn't count.\n                for fv in range(1, f+1):\n                    memo[tv] += memo[tv-fv] if tv-fv>=0 else 0\n                memo[tv] %= maxV \n        return memo[-1]\n        \n        '''\n        memo = {}\n        x = 10**9+7\n        def bt(remD, remT):\n            if remT<0 or remD<0:\n                return 0\n            if (remD, remT) in memo:\n                return memo[(remD, remT)]\n            if remD==0:\n                return 1 if remT==0 else 0\n            temp = 0\n            for i in range(1, f+1):\n                temp += bt(remD-1, remT-i)\n            temp %= x\n            memo[(remD, remT)] = temp\n            return temp\n        \n        return bt(d, target)\n        '''\n    \n    '''\n    (a+b)%c = (a%c+b%c)%c\n    \n    '''\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        modulo = 10**9 + 7\n        dp = [[0 for i in range(target+1)] for j in range(d+1)]\n        for dd in range(1, d+1):\n            for tt in range(dd, min(target, dd * f)+1):\n                if dd == 1:\n                    dp[dd][tt] = 1\n                else:\n                    start =max( tt - f, 1)\n                    end = tt - 1\n                    dp[dd][tt] = sum(dp[dd-1][start:end+1])\n                    \n        return dp[d][target] % modulo\n'''\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        modulo = 10**9 + 7\n        #don't use row 0 and all column 0 \n        dp = [[0 for i in range(target+1)] for j in range(d+1)]\n        \n        #from die No. 1 to d\n        for dd in range(1, d+1):\n            #for target from 0 to min(f*dd, target)\n            for tt in range(dd, min(f * dd, target) + 1 ):\n                if dd == 1:\n                    dp[dd][tt] = 1\n                else:\n                    end   = tt - 1\n                    start = max(1, tt - f)\n                    dp[dd][tt] = sum(dp[dd-1][start:end+1])\n    \n        return dp[d][target] % modulo                          \n        \n  \n        #f(d, target) = f(d-1, target-1) + f(d-1, target-2) + ... + f(d-1, target-f)  assuming target > f\n        modulo = 10**9 + 7\n        cache = {}\n        def numRollsToTargetHelper(dd, tt):\n            if cache.get((dd,tt)) != None:\n                return cache[(dd,tt)]\n            nonlocal f\n            if dd == 1:\n                if tt <= f:\n                    return 1\n                else:\n                    return 0\n            \n            ret = 0\n            for i in range(1, f+1):\n                if tt - i > 0:\n                    ret += numRollsToTargetHelper(dd-1, tt-i)\n            cache[(dd,tt)] = ret\n            return ret\n        \n        ret = numRollsToTargetHelper(d, target)\n        return ret % modulo\n        '''       ", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        n = target\n        ways = [[0 for i in range(n+1)] for j in range(d+1)]\n        \n        ways[0][0] = 1\n        \n        for i in range(1,d+1):\n            for j in range(n+1):\n                c = 0\n                for k in range(1,f+1):\n                    c += ways[i-1][j-k] if j-k>=0 else 0\n                    \n                ways[i][j] = c\n                \n        #print(ways)\n        return ways[d][n]%(10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(target+1)]]\n        #dp.append([0 for _ in range(target+1)])\n        for i in range(1,min(f+1,target+1)):\n            dp[0][i] = 1 \n        for i in range(2,d+1):\n            dp.append([0 for _ in range(target+1)])\n            for t in range(i,target+1):\n                for d in range(1,min(t,f+1,target+1)):\n                    if t - d >= 0 and dp[-2][t-d]:\n                        dp[-1][t] += dp[-2][t - d]\n            dp.pop(0)\n        return (dp[0][-1]) % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        MOD = 10 ** 9 + 7\n        dp = [0] * (target + 1)\n        dp[0] = 1\n        for i in range(1, d + 1):\n            for t in reversed(range(target + 1)):\n                dp[t] = sum(dp[t - j] if t - j >= 0 else 0 for j in range(1, f + 1)) % MOD\n        return dp[target]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [0] * (target + 1)\n        dp[0] = 1\n        M = 10 ** 9  + 7\n        for i in range(d):\n            n_dp = [0] * (target + 1)\n            for j in range(target + 1):\n                for m in range(1, f + 1):\n                    if j + m > target:\n                        break\n                    \n                    n_dp[j + m] += dp[j]\n            \n            dp = [k % M for k in n_dp]\n        \n        return dp[-1]", "from collections import defaultdict\n\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = defaultdict(int)\n        \n        def helper(d, target):\n            if d == 0:\n                return 1 if target == 0 else 0\n            if (d, target) in memo:\n                return memo[(d, target)]\n\n\n            for c in range(1, f + 1):\n            #for c in range(max(0, target-f), target):\n                memo[(d, target)] += helper(d - 1, target - c)\n                #memo[(d, target)] += helper(d - 1, c)   \n            return memo[(d, target)]\n        return helper(d, target) % (10**9 + 7)\n    \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp = [[0] * (target+1) for _ in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                for k in range(1, min(f,j)+1):\n                    dp[i][j] += dp[i-1][j-k]         \n            # print(dp)\n        return dp[-1][-1] % (10**9 + 7)\n    \n#         if target > d*f:\n#             return 0\n#         dicti = collections.defaultdict(int)\n#         def dice_target(rem_dice, summ):\n#             if rem_dice == 0:\n#                 return 1 if summ == target else 0\n#             if summ > target:\n#                 return 0\n#             if (rem_dice, summ) in dicti:\n#                 return dicti[rem_dice, summ]\n\n#             for i in range(1, f+1):\n#                 dicti[rem_dice, summ] += dice_target(rem_dice-1, summ+i)\n#             return dicti[rem_dice, summ]\n        \n        \n#         return dice_target(d, 0) % (10**9 + 7)\n\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [0] * (target + 1)\n        dp[0] = 1\n        for i in range(d):\n            dp_new = [0] * len(dp)\n            for i in range(1, len(dp)):\n                for j in range(1, f + 1):\n                    if i - j >= 0:\n                        dp_new[i] = (dp_new[i] + dp[i - j]) % (10**9 + 7)\n            dp = dp_new\n        return dp[-1]  % (10**9 + 7)\n", "class Solution:\n    cache = {}\n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d == 1:\n            if f < target:\n                return 0\n            else:\n                return 1\n\n        if (d, f, target) in self.cache:\n            return self.cache[(d, f, target)]\n        else:\n            num = sum(self.numRollsToTarget(d-1, f, target-i) for i in range(1, min(f+1, target))) % (10**9 + 7)\n            self.cache[(d, f, target)] = num\n        \n        return num\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def dp(d, target):\n            if d == 0:\n                return 0 if target > 0 else 1\n            if (d, target) in memo:\n                return memo[(d, target)]\n            to_return = 0\n            for k in range(max(0, target-f), target):\n                to_return += dp(d-1, k)\n            memo[(d, target)] = to_return\n            return to_return\n        return dp(d, target) % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target < d or target > d * f:\n            return 0\n        \n        total_sum = 0\n        cache_sum = []\n        \n        if target > d * (1 + f) / 2:\n            target = d * (1 + f) - target\n        \n        for i in range(target, -1, -1):\n            num = 0 if i > f else 1\n            total_sum += num; \n            cache_sum.append(total_sum)\n        cache_sum = cache_sum[::-1]\n        cache_sum[0] = cache_sum[1]\n        \n        for i in range(2, d+1):\n            total_sum = 0\n            for j in range(target, -1, -1):\n                total_sum += cache_sum[max(j-f, 0)] - cache_sum[j]\n                cache_sum[j] = total_sum\n        return cache_sum[-1] % (10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        modulo = 10**9 + 7\n        dp = [[0 for i in range(target+1)] for j in range(d+1)]\n        \n        for dd in range(1, d+1):\n            for tt in range(dd, min(f*dd, target) + 1):\n                if dd == 1:\n                    dp[dd][tt] = 1\n                else:\n                    end = tt - 1\n                    start = max(1, tt-f)\n                    dp[dd][tt] = sum(dp[dd-1][start:end+1])\n        \n        return dp[d][target] % modulo", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0] * (d + 1) for _ in range(target+1)]\n        dp[0][0] = 1\n        for i in range(1, target+1):\n            for j in range(1, d + 1):\n                if i >= j:\n                    for num in range(1, min(i, f) + 1):\n                        dp[i][j] += dp[i-num][j - 1]\n        return dp[-1][-1] % (10 ** 9 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for j in range(target+1)] for i in range(d)]\n        for j in range(1, min(f, target)+1):\n            dp[0][j] = 1\n        for i in range(1, d):\n            for j in range(1, target+1):\n                for k in range(1, f+1):\n                    if j < k:\n                        break\n                    dp[i][j] += dp[i-1][j-k]\n        return dp[d-1][target] % (10**9 + 7)\n                \n                \n", "from collections import defaultdict\n\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = defaultdict(int)\n        \n        def helper(d, target):\n            if d == 0:\n                return 1 if target == 0 else 0\n            if (d, target) in memo:\n                return memo[(d, target)]\n            else:\n                for c in range(1, f + 1):\n                    memo[(d, target)] += helper(d - 1, target - c)\n                return memo[(d, target)]\n        return helper(d, target) % (10**9 + 7)\n    \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp={}\n        for k in range(1,f+1):\n            dp[(1,k)]=1\n            \n        def dfs_num_rolls(dice_left,tot_left):\n\n            if tot_left>f**(dice_left) or tot_left<0 or dice_left==0:\n                dp[(dice_left,tot_left)]=0\n                return 0\n            if (dice_left,tot_left) in dp:\n                return dp[(dice_left,tot_left)]\n            \n            total=0\n            for k in range(1,f+1):\n                total+=dfs_num_rolls(dice_left-1,tot_left-k)%(10**9+7)\n            \n            total=total%(10**9+7)\n            dp[(dice_left,tot_left)]=total\n            return total\n        \n        dfs_num_rolls(d,target)\n        return dp[(d,target)]\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        dp[0][0] = 1 #d=0 and target=0\n        \n        for i in range(1,d+1):\n            for j in range(1,target+1):\n                for k in range(1,min(j,f)+1):\n                    dp[i][j] += dp[i-1][j-k]\n                    \n        return dp[d][target]%(10**9+7)\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def rec(d,target):\n            if d==0:\n                if target==0: \n                    return 1\n                else:\n                    return 0\n            if target<=0:\n                return 0\n            if (d,target) in memo:\n                return memo[(d,target)]\n            count = 0\n            for i in range(1,f+1):\n                count += rec(d-1, target-i)\n            memo[(d,target)] = count   \n            return count\n        return rec(d,target)%((10**9)+7)\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        #dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        dp = [0 for _ in range(target+1)]\n        dp[0] = 1\n        #dp[0][0] = 1\n        \n        for i in range(1, d+1):\n            new = [0]\n            for j in range(1, target+1):\n                new.append(0)\n                for k in range(1, f+1):\n                    if j-k>=0:\n                        new[-1]=(new[-1]+dp[j-k])%(10**9+7)\n                        #dp[i][j]+=dp[i-1][j-k]\n                    else:\n                        break\n            dp = new             \n        return dp[-1]\n        return dp[-1][-1]%(10**9+7)\n                \n                \n    \n    '''\n    f = 6\n    \n     01234567\n    010000000\n    101111110\n    200123456\n         \n         \n         \n    '''", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        \n        dp = [ [0]*(target+1) for _ in range(d) ]\n        \n        l = min(target+1, f+1)\n        \n        for i in range(1,l):\n            dp[0][i] = 1\n        \n        for level in range(1,d):\n            \n            #print(dp[level-1], dp[level])\n            for face in range(1,f+1):\n                for t in range(1,target+1):\n                \n                \n                #for face in range(1,f+1):\n                    \n                    if t - face > 0:\n                        dp[level][t] += dp[level-1][t-face]\n        \n        #print(dp)\n        return dp[-1][-1] % (10**9 + 7)\n        \n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        dp[0][0] = 1 #d=0 and target=0\n        \n        for i in range(1,d+1):\n            for j in range(1,target+1):\n                for k in range(1,min(j,f)+1):\n                    dp[i][j] += dp[i-1][j-k]\n                    \n        return dp[d][target]%(10**9+7)\n        \n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for x in range(target + 1)] for y in range(d + 1)]\n        dp[0][0] = 1\n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                for k in range(1, min(j, f) + 1):\n                    dp[i][j] += dp[i - 1][j - k]\n        return dp[d][target] % (10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        dp[0][0] = 1\n        \n        for i in range(1,d+1):\n            for j in range(1, target+1):\n                for k in range(1, f+1):\n                    if k<=j:\n                        dp[i][j] += dp[i-1][j-k]\n        \n        \n        return dp[d][target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        def helper(d, target, map):\n            if (d,target) in map:\n                return map[(d,target)]\n            if d == target:\n                return 1\n            elif d == 0 or target < d:\n                return 0\n            map[(d,target)] = 0\n            for num in range(1,f+1):\n                map[(d,target)] += helper((d-1), (target-num), map)\n            return map[(d,target)]\n        helperMap = {}\n        return (helper(d,target,helperMap)%(10**9+7))", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        dp[0][0] = 1\n        m = (10**9 + 7)\n        \n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                for k in range(1, f+1):\n                    if k<=j:\n                        dp[i][j] += dp[i-1][j-k]\n\n        return dp[d][target]%m;\n                        \n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10**9 + 7\n        dp = [[0] * (target + 1) for i in range(d + 1)]\n        \n        dp[0][0] = 1\n        for i in range(1, d + 1):\n            nxt = [[0] * (target + 1) for i in range(d + 1)]\n            for j in range(1, target + 1):\n                nxt[i][j] = sum(dp[i-1][j - x] for x in range(1, f + 1) if j >= x) % mod\n            dp = nxt\n        return dp[-1][-1]\n                \n        \n        \n        # mod = 10**9 + 7\n        # @lru_cache(None)\n        # def dfs(d, curr):\n        #     if d == 0:\n        #         return curr == 0\n        #     if d < 0 or curr < 0:\n        #         return 0\n        #     return sum(dfs(d - 1, curr - x) for x in range(1, f + 1)) % mod\n        # return dfs(d, target)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        \n        dp = [ [0]*(target+1) for _ in range(d) ]\n        \n        l = min(target+1, f+1)\n        \n        for i in range(1,l):\n            dp[0][i] = 1\n        \n        for level in range(1,d):\n\n            #for face in range(1,f+1):\n            for t in range(1,target+1):\n                \n                \n                for face in range(1,f+1):\n                    \n                    if t - face > 0:\n                        dp[level][t] += dp[level-1][t-face]\n        \n        #print(dp)\n        return dp[-1][-1] % (10**9 + 7)\n        \n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        #dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        dp = [0 for _ in range(target+1)]\n        dp[0] = 1\n        #dp[0][0] = 1\n        \n        for i in range(1, d+1):\n            new = [0]\n            for j in range(1, target+1):\n                new.append(0)\n                for k in range(1, f+1):\n                    if j-k>=0:\n                        new[-1]=(new[-1]+dp[j-k])%(10**9+7)\n                        #dp[i][j]+=dp[i-1][j-k]\n            dp = new             \n        return dp[-1]\n        return dp[-1][-1]%(10**9+7)\n                \n                \n    \n    '''\n    f = 6\n    \n     01234567\n    010000000\n    101111110\n    200123456\n         \n         \n         \n    '''", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # # 1-d\n        # dp = [0] * (target+1)\n        # for i in range(1,min(f+1,target+1)):\n        #     dp[i] = 1\n        # for _ in range(d-1):\n        #     for j in reversed(range(1,len(dp))):\n        #         dp[j] = 0\n        #         for num in range(1,f+1):\n        #             if 0<=j-num:\n        #                 dp[j] += dp[j-num]\n        # return dp[-1] % (10**9 + 7)\n        \n        \n        # 2-d\n        dp = [[0]*(target+1) for i in range(d)]\n        for i in range(1,min(target+1,f+1)):\n            dp[0][i] = 1\n        for i in range(1,d):\n            for j in range(1,target+1):\n                for num in range(1,f+1):\n                    if j-num >= 0:\n                        dp[i][j] += dp[i-1][j-num]\n        return dp[-1][-1] % (10**9 + 7)\n    \n    \n    \n    \n\n", "\nclass Solution:\n    # mod = 1e9+7\n\n        \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = dict()\n        \n        def fun(d, target):\n            mod = int(1e9+7)\n            if(target==0 and d==0):\n                return 1\n            if(target==0 and d!=0):\n                return 0\n            if(target<0):\n                return 0\n            if(d==0):\n                return 0\n            if((d, target) in dp):\n                return dp[d, target]\n            tmp = 0\n            for i in range(1,f+1):\n                tmp += (fun(d-1, target-i))%mod\n                tmp %= mod\n            dp[d, target] = tmp\n            return tmp\n        return fun(d, target)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0]*(target + 1) for i in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                for k in range(1, min(j, f) + 1):\n                    dp[i][j] =  dp[i][j] + dp[i-1][j-k]\n                    \n        return dp[i][j] % (10**9 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        arr = [[0 for i in range(target+1)] for i in range(d)]\n        \n        for i in range(1, min(f, target)+1):\n            arr[0][i] = 1\n            \n        for row in range(1, d):\n            temp = 0\n            for col in range(row+1, target+1):\n                temp += arr[row-1][col-1]\n                if col >= f+1:\n                    temp -= arr[row-1][col-f-1]\n\n                arr[row][col] = temp\n                \n        # for i in range(len(arr)):\n        #     print(i, arr[i])\n            \n        return arr[d-1][target]%(1000000007)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if(d>target or (d==1 and target>f)):\n            return 0\n        if(d == target or d == 1):\n            return 1\n        dp = [[0 for i in range(target+1)] for j in range(2)]\n        dp_1 = [0 for i in range(target+1)]\n        for i in range(1,min(target+1,f+1)):\n            dp_1[i] = 1\n        dp[0] = dp_1\n        for i in range(2,d+1):\n            dp[1] = [0 for i in range(target+1)]\n            for j in range(i,target+1):\n                if(i==j):\n                    dp[1][j] = 1\n                    continue\n                for k in range(1,min(j+1,f+1)):\n                    dp[1][j] += dp[0][j-k]*dp_1[k]\n            dp[0] = dp[1]\n        # print(dp,dp_1)\n        return dp[1][-1]%1000000007", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp=[[0 for i in range(target+1)] for j in range(d+1)]\n        dp[0][0]=1\n        for i in range(1,d+1):\n            for j in range(1,target+1):\n                for k in range(1,f+1):\n                    \n                    if(j>=k):\n                        dp[i][j]+=dp[i-1][j-k]\n                        \n        return dp[-1][-1]%((10**9)+7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = int(10**9 + 7)\n        dp = [[0] * (target+1) for _ in range(d+1)] \n        for j in range(1, min(f+1, target+1)): dp[1][j] = 1\n        for i in range(2, d+1):\n            for j in range(1, target+1):\n                for k in range(1, f+1):\n                    if j - k >= 0: dp[i][j] += dp[i-1][j-k]\n                dp[i][j] %= mod        \n        return dp[-1][-1]\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(target + 1)] for _ in range(d + 1)]\n        \n        dp[0][0] = 1\n        \n        # Iterate through every dice\n        for i in range(1, d+1):\n            \n            # iterate through every target\n            for j in range(1, target+1):\n                \n                # go through every possible value on dice\n                for k in range(1, f+1):\n                    if k <= j:\n                        dp[i][j] += dp[i-1][j - k]\n                        \n        return dp[-1][-1] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0]*(target+1) for i in range(d+1)]\n        dp[0][0] = 1\n        mod = (10**9)+7\n        for i in range(1,d+1):\n            for j in range(target+1):\n                for k in range(1,f+1):\n                    if j-k >=0:\n                        dp[i][j] += dp[i-1][j-k]\n        return dp[d][target] % mod\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0] * target for _ in range(d)]\n        \n        for i in range(d):\n            for j in range(target):\n                if i == 0 and j+1 <= f:\n                    dp[i][j] = 1\n                elif i == 0:\n                    dp[i][j] = 0\n                elif j >= i:\n                    for k in range(1, f+1):\n                        if j - k >= 0:\n                            dp[i][j] += dp[i-1][j-k]\n        \n        # print(dp)\n        return dp[d-1][target-1] % 1000000007", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target == 0:\n            return 0\n        dp = [[0] * (target + 1) for _ in range(d + 1)]\n        dp[0][0] = 1\n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                for num in range(1, f + 1):\n                    if j - num >= 0:\n                        dp[i][j] += dp[i-1][j-num]\n        \n        return dp[d][target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        memo = {}\n        \n        def dpWays(d, target):\n            \n            if d == 0:\n                \n                return(0 if target > 0 else 1)\n            \n            if (d, target) in memo:\n                \n                return(memo[(d, target)])\n            \n            to_return = 0\n            \n            for k in range(max(0, target - f), target):\n                \n                to_return += dpWays(d-1, k)\n                \n            memo[(d, target)] = to_return\n            \n            return(to_return)\n        \n        return(dpWays(d, target) % (10**9 + 7))", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # dp(depth, f, target) = 1+dp(depth-1, f, target-face_chosen) for f_c in range(1,f+1)\n        \n        opt = [[0]*(target+1) for _ in range(d+1)]\n        opt[0][0]=1\n        mod = 10**9 +7\n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                # we need to get sum of all arrows out\n                sum_children = 0\n                face_val = 1\n                while face_val <=f and j-face_val>=0 :\n                    sum_children+= opt[i-1][j-face_val]%mod\n                    face_val+=1\n                opt[i][j] = sum_children%mod\n        # print(opt[1])\n        # print(opt[0])\n        return opt[d][target]\n                    \n        \n        \n#         for d in range()\n        \n        \n        \n        \n        \n#         opt(i, j) = 1+sum(opt(i-1, j-face) for face in range(1, f+1))\n        \n        \n        \n#         we want opt(d=d, f=f, sum_=target)\n        \n        \n        \n#         prev_map = dict()\n#         for face in range(2, f+1):\n#             prev_map[face]=1\n        \n#         for dice in range(1, d+1):\n#             new_map = dict()\n#             for face in range(1, face):\n#                 for i, count in prev_map.items():\n#                     new_map[face+i]=count+i\n#             new_map = prev_map\n            \n#         print(prev_map)\n#         return prev_map[target]\n                \n            \n", "class Solution:\n    # Recursive memoized solution\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def num_rolls_util(level, target):\n            if level * f < target or target < level:\n                return 0\n            if level == 0:\n                return 1\n            \n            res = 0\n            for i in range(max(0, target - f), target):\n                if (level-1, i) in memo:\n                    res += memo[(level-1, i)]\n                else:\n                    tmp = num_rolls_util(level - 1, i)\n                    memo[(level-1, i)] = tmp\n                    res += tmp\n\n            return res % (10 ** 9 + 7)\n        \n        return num_rolls_util(d, target)\n    \n    \n    '''\n    if target < d or target > d * f:\n            return 0\n        if target > (d*(1+f)/2):\n            target = d * (1 + f) - target\n        dp = [0] * (target + 1) \n        for i in range(1, min(f, target) + 1):\n            dp[i] = 1\n        for i in range(2, d + 1):\n            new_dp = [0] * (target + 1)\n            for j in range(i, min(target, i * f) + 1):\n                new_dp[j] = new_dp[j - 1] + dp[j - 1]\n                if j - 1 > f:\n                    new_dp[j] -= dp[j - f - 1]\n            dp = new_dp\n\n        return dp[target] % (10 ** 9 + 7)\n    '''", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(max(target+1,f+1))] for _ in range(d+1)]\n        # boundary condition dp[1][1],dp[1][2],...,dp[1][f]\n        for i in range(1,f+1):\n            dp[1][i] = 1\n        # dp[dice][values]= dp[dice-1][values-1] + \n        for dice in range(1,d+1):\n            for values in range(1,target+1):\n                for i in range(1,f+1):\n                    if values-i <1:\n                        break\n                    dp[dice][values]+=dp[dice-1][values-i]\n        return dp[d][target] % (10**9+7)\n                \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # dp[i][j]: \u7528i\u4e2a\u9ab0\u5b50\u6254\u51fa\u548c\u4e3aj\u7684\u65b9\u6cd5\u603b\u6570\n        dp = [[0] * (target+1) for _ in range(d+1)]\n        m = 10**9+7\n        dp[0][0] = 1 # \u7531\u4e8e\u6bcf\u4e2a\u9ab0\u5b50\u5fc5\u9009\uff0cdp[i][0], i != 0\u7684\u610f\u601d\u662f\uff0c\u524di\u4e2a\u9ab0\u5b50\u90fd\u4e0d\u9009\uff0c\u662f\u4e0d\u53ef\u4ee5\u7684\uff0c\u6240\u4ee5\u4e3a0\n        for i in range(1, d+1): \n            for j in range(i, target-d+i+1): # \u7531\u4e8e\u540e\u9762\u6709d-j\u4e2a\u9ab0\u5b50\uff0c\u6240\u4ee5\u6211\u4eec\u524di\u4e2a\u4e0d\u7528\u6254\u6ee1target\n                for k in range(1, min(j, f)+1): # \u53ea\u53ef\u80fd\u6254\u5230j\uff0c\u5982\u679cf\u8d85\u8fc7\u4e86j\uff0c\u6211\u4eec\u4e0d\u8981\n                    dp[i][j] += dp[i-1][j-k] % m\n\n        return dp[d][target] % m\n\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        z = 10**9+7\n        def sol(n,m,t):\n            \n            dp=[[0 for i in range(t+1)] for j in range(n+1)]\n            \n            for i in range(1,min(t+1,m+1)):\n                dp[1][i]=1\n            \n            for i in range(1,n+1):\n                for j in range(1,t+1):\n                    for k in range(1,min(j,m+1)):\n                           dp[i][j]+=(dp[i-1][j-k])% z\n                    \n            return dp[n][t]%z\n                          \n        return sol(d,f,target)%z\n                          \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp = [[0 for j in range(target + 1)] for i in range(d + 1)]\n        dp[0][0] = 1\n        for i in range(d):\n            for ff in range(1, f + 1):\n                for sm in range(target):\n                    if sm + ff <= target:\n                        dp[i + 1][sm + ff] += dp[i][sm]\n        return dp[d][target]%(10**9 + 7)\n\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        \n        dp[0][0] = 1\n        \n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                for k in range(1, f+1):\n                    if j-k>=0:\n                        dp[i][j]+=dp[i-1][j-k]\n        return dp[-1][-1]%(10**9+7)\n                \n                \n    \n    '''\n    f = 6\n    \n     01234567\n    010000000\n    101111110\n    200123456\n         \n         \n         \n    '''", "class Solution:\n    def numRollsToTarget(self, d, f, target):\n        \n        if d == 0:\n            return 0\n        \n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        \n        \n        \n        for i in range(1, target+1):\n            dp[0][i] = 0\n        for j in range(1, d+1):\n            dp[j][0] = 0\n            \n        dp[0][0] = 1\n        \n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                for k in range(1, f+1):\n                    if j-k >= 0:\n                        dp[i][j] += dp[i-1][j-k]\n                        \n        return dp[d][target] % ((10 ** 9) + 7)\n                \n                \n#         def recursive(d, f, target):\n            \n#             if target == 0 and d == 0:\n#                 return 1\n            \n#             if target < 0 or d == 0:\n#                 return 0\n            \n#             if dp[d][target] != -1:\n#                 return dp[d][target]\n#             temp = 0\n#             for i in range(1, f+1):\n#                 temp += recursive(d - 1, f, target - i)\n                \n#             dp[d][target] =  temp\n#             return dp[d][target]\n\n#         return (recursive(d, f, target) % ((10 ** 9) + 7))\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        def dfs(d, target):\n            if (d, target) in cache:\n                return cache[(d, target)]\n            if target < 0 or d < 0:\n                return 0\n            if target == 0 and d == 0:\n                return 1\n            ways = 0\n            for i in range(1, f + 1):\n                ways += dfs(d - 1, target - i)\n            cache[(d, target)] = ways\n            return ways\n\n        cache = {}\n        mod = 10 ** 9 + 7\n        return dfs(d, target) % mod\n\n        # mod = 10 ** 9 + 7\n        # dp = [[0] * (target + 1) for _ in range(d + 1)]\n        # # dp[0][0] = 1\n        # for i in range(1, min(f, target) + 1):\n        #     dp[1][i] = 1\n        # for i in range(2, d + 1):\n        #     # the numbers that can be reached by rolling i dice\n        #     for num in range(i, min(i * f, target) + 1):\n        #         for diceNum in range(1, (f + 1)):\n        #             if num - diceNum >= 1:\n        #                 dp[i][num] += dp[i - 1][num - diceNum]\n        #             else:\n        #                 break\n        # return dp[d][target] % mod\n\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        MOD=10**9+7\n        dp=[[0 for i in range(target+1)] for i in range(d+1)]\n        \n        for j in range(1,min(f+1,target+1)):\n            dp[1][j]=1\n        \n        for i in range(1,d+1):\n            for j in range(target+1):\n                for k in range(1,min(f+1,j)):\n                    dp[i][j]+=dp[i-1][j-k]%MOD\n        \n        return dp[d][target]%MOD", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo={}\n        def dp(dice,target):\n            if((dice,target) in memo):\n                return memo[(dice,target)]\n            if(dice<=0 or target<=0):\n                return 0\n            if(dice==1):\n                if(target>=1 and target<=f):\n                    return 1\n                else:\n                    return 0\n            rolls=0\n            for i in range(1,f+1):\n                rolls+=dp(dice-1,target-i)%1000000007\n            memo[(dice,target)]=rolls%1000000007\n            return memo[(dice,target)]%1000000007\n        return dp(d,target)%1000000007", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp1 = [0 for _ in range(target+1)]\n        dp2 = [0 for _ in range(target+1)]\n        dp1[0] = 1\n        mod = 10 ** 9 + 7\n        for i in range(1, d+1):\n            for j in range(target+1):\n                for k in range(1, min(j,f) + 1):\n                    dp2[j] = (dp2[j] + dp1[j-k]) % mod\n            dp1 = dp2\n            dp2 = [0 for _ in range(target+1)]\n        return dp1[target] % mod", "class Solution:\n    # Recursive memoized solution\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def num_rolls_util(level, target):\n            if level * f < target or target < level:\n                return 0\n            if level == 0:\n                return 1\n            \n            res = 0\n            for i in range(max(0, target - f), target):\n                if (level-1, i) in memo:\n                    res += memo[(level-1, i)]\n                else:\n                    tmp = num_rolls_util(level - 1, i)\n                    memo[(level-1, i)] = tmp\n                    res += tmp\n\n            return res % (10 ** 9 + 7)\n        \n        return num_rolls_util(d, target)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if(d==1):\n            return int(f>=target)\n        dp = [[0]*target for _ in range(d)]\n        f = min(f, target)\n        for i in range(f):\n            dp[0][i] = 1\n        for i in range(1, d):\n            for j in range(i, target):\n                for face in range(1, f+1):\n                    if(face > j):\n                        break\n                    dp[i][j] = (dp[i-1][j-face]+dp[i][j])%(1e9+7)\n        return int(dp[-1][-1])", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [ [ 0 for j in range(target + 1) ] for i in range(d) ]\n        \n        for i in range(f):\n            if i+1 <= target:\n                dp[0][i+1] = 1\n        \n        for i in range(1, d):\n            for j in range(1, target + 1):\n                k = 1\n                while j - k > 0 and k <= f:\n                    dp[i][j] += dp[i-1][j-k]\n                    k += 1\n        return dp[-1][-1] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        A = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        A[0][0] = 1\n        mod = 10 ** 9 + 7\n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                for k in range(1, min(j,f)+1):\n                    A[i][j] = (A[i][j] + A[i-1][j-k]) % mod\n        return A[-1][-1]", "class Solution:    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dpt = [[1 if (i == 0 and 0<j and j <= f) else 0 for j in range(target+1)] for i in range(d)]\n        for i in range(1,d):\n            for j in range(1,target+1):\n                for k in range(1,f+1):\n                    if(j-k >= 0):\n                        dpt[i][j] += dpt[i-1][j-k] % (10**9+7)\n        return dpt[-1][target] % (10**9+7)\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for j in range(d + 1)] for i in range(target + 1)]\n        dp[0][0] = 1    \n        for i in range(1, target + 1):\n            for j in range(1, d + 1):\n                for k in range(1, f + 1):\n                    if target - k >= 0:\n                        dp[i][j] += dp[i - k][j - 1]\n                        \n                    \n        \n        return dp[target][d] % (10**9 + 7)      \n                    \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        self.sols = {}\n        self.sols[(d, f, target)] = self.iter(d, f, target)\n        return self.sols[(d, f, target)] % (10**9 + 7)\n    def iter(self, d, f, target):\n        if d == 0:\n            return 1 if target == 0 else 0\n        if (d, f, target) in self.sols: return self.sols[(d, f, target)]\n        self.sols[(d, f, target)] =  sum([self.iter(d-1, f, target-i) for i in range(1,f+1)])\n        return self.sols[(d, f, target)]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:        \n        # dp\n        dp = [[0 for i in range(target + 1)] for j in range(d + 1)]\n        dp[0][0] =  1\n        mod =  10**9 + 7\n        for i in range(1, d+1):\n            for j in range(1, target + 1):\n                for k in range(1, min(f, j) + 1):\n                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod\n        return dp[d][target] % mod\n        \n        \n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        MOD=(10**9)+7\n        mem=[]\n        for di in range(d+1):\n            cr=[0 for i in range(target+1)]\n            #cr=[1 if (i>0 and di==1 and i<=f) else 0 for i in range(target+1)]\n            #cr=[0 if (i>f or di!=1 or i<1) else 1 for i in range(target+1)]\n            mem.append(cr)\n        mem[0][0]=1\n        print(mem)\n        for ti in range(1,target+1):\n            for di in range(1,d+1):\n                for fi in range(1,f+1):\n                    if(ti-fi>=0):\n                        mem[di][ti]+=mem[di-1][ti-fi];\n        \n        #print(mem)\n        return mem[d][target]%MOD", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        def numRollsHelper(level, target):\n            if f * level < target or target < level:\n                return 0\n            \n            if level == 0:\n                return 1\n            \n            res = 0\n            for i in range(max(target - f, 0), target):\n                if (level - 1, i) in memo:\n                    res += memo[(level - 1, i)]\n                else:\n                    tmp = numRollsHelper(level - 1, i)\n                    memo[(level - 1, i)] = tmp % (10 ** 9 + 7)\n                    res += tmp % (10 ** 9 + 7)\n            \n            return res\n        \n        memo = {}\n        return numRollsHelper(d, target) % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        M = 10**9+7\n        dp = [[0 for j in range(max(target, f)+1)] for i in range(d+1)]\n        for j in range(1, f+1):\n            dp[1][j] = 1\n            \n        for i in range(2, d+1):\n            for j in range(i, max(target, f)+1):\n                # print(\\\"i\\\", i, \\\"j\\\", j)\n                for k in range(1, f+1):\n                    if j>=k:\n                        dp[i][j] += dp[i-1][j-k]\n        \n            \n        # for i in range(d+1):\n        #     print(dp[i])\n            \n        return dp[-1][target] % M\n    \n# 1\n# 6\n# 3\n# 2\n# 6\n# 7\n# 2\n# 5\n# 10\n# 30\n# 30\n# 500\n", "class Solution:\n    \n    def __init__(self):\n        self.cache = dict()\n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        def helper (d, r):\n            \n            if d < 0 or r < 0:\n                return 0\n            \n            if d == 0 and r == 0:\n                return 1\n                \n            elif d != 0 and r != 0:\n                \n                if (d, r) not in self.cache:\n                \n                    self.cache[(d, r)] = 0\n                \n                    for i in range(1, f+1):\n                        self.cache[(d, r)] += helper(d - 1, r - i)\n                        \n                return self.cache[(d, r)]\n            \n            else:\n                return 0\n            \n        \n        return helper(d, target) % (10**9 + 7)\n", "# factorials = [1]\n\n# def choose(n,r):\n#     nonlocal factorials\n#     return factorials[n]/(factorials[n-r]*factorials[r])\n\n# def counter(d,f,target,facesUsed, d_og, t_og):\n#     if(d==0 and target==0):\n#         return factorials[d_og]\n#     if(d<0 or target<0 or f<1):\n#         return 0\n#     # print(d,f,target,facesUsed, min(target//f + 1,d))\n#     c = 0\n#     for i in range(min(target//f,d)+1):\n#         a = counter(d-i,f-1,target-f*i,facesUsed + 0 if i==0 else 1,d_og,t_og) / factorials[i]\n#         c += a\n#     return c\n        \nclass Solution:    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # nonlocal factorials\n        # for i in range(1,d+1):\n        #     factorials.append(i*factorials[i-1])\n        # return int(counter(d,f,target,0,d,target))\n        dpt = [[1 if (i == 0 and 0<j and j <= f) else 0 for j in range(target+1)] for i in range(d)]\n        # for i in range(d):\n            # for j in range(min(,target):\n        for i in range(1,d):\n            for j in range(1,target+1):\n                for k in range(1,f+1):\n                    if(j-k >= 0):\n                        dpt[i][j] += dpt[i-1][j-k] % (10**9+7)\n        # print(dpt)\n        return dpt[-1][target] % (10**9+7)\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [1]+[0]*target\n        \n        for i in range(1, d+1):\n            dp2 = [0]*(target+1)\n            for j in range(target, i-1, -1):\n                for k in range(1, f+1):\n                    if j-k<i-1: break\n                    \n                    dp2[j] += dp[j-k]\n                dp2[j]%=(10**9+7)\n            dp = dp2\n        # print(dp)\n        return dp[-1]", "class Solution:\n    def numRollsToTarget(self, dice: int, faces: int, target: int) -> int:\n        \n        table = [[0 for _ in range(target + 1)] for _ in range(dice + 1)]\n        table[0][0] = 1\n        mod = 10 ** 9 + 7\n        \n        for d in range(1, dice + 1):\n            for i in range(1, target + 1):\n                for f in range(1, min(i + 1, faces + 1)):\n                    table[d][i] = (table[d][i] + table[d-1][i-f]) % mod\n                \n        return table[-1][-1]", "class Solution:\n    def numRollsToTarget(self, N: int, faces: int, total: int) -> int:\n        DP = {}\n        DP[0] = [0] * (total+1)\n        DP[1] = [0] + [1]*(faces) + [0] *(total-faces)\n\n        for die in range(2,N+1):\n            DP[die] = [0] * (total+1)\n            for i in range(1,total+1):#the subtotal\n                count  = 0\n                for j in range(1,faces+1):#this die's contribution\n                    if (i-j) >= 1 and DP[die-1][i-j] > 0:\n                        if die==2:\n                            print((i,j))\n                        count+= DP[die-1][i-j]\n                DP[die][i] = count\n                print(count)\n        ans = DP[N][total]\n        return ans %(10**9 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp=[[0 for i in range(target+1)] for _ in range(d+1)]\n        dp[0][0]=1\n        for i in range(1,d+1):\n            for j in range(1,target+1):\n                for k in range(1,f+1):\n                    if j-k>=0:\n                        dp[i][j]+=dp[i-1][j-k]\n                        \n        return dp[-1][-1]%(10**9+7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(d)] for _ in range(target+1)]\n        \n        for i in range(1, target+1):\n            dp[i][0] = 1 if i <= f else 0\n\n        for di in range(1, d):\n            for t in range(1, target+1):\n                sub_targets = [t-face if t >= face else 0 for face in range(1, f+1)]\n                dp[t][di] = sum([dp[sub][di-1] for sub in sub_targets])\n        \n        return dp[-1][-1] % (10 ** 9 + 7)\n            \n            \n", "class Solution:\n    # Recursive memoized solution\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def num_rolls_util(level, target):\n            if level * f < target or target < level:\n                return 0\n            if level == 0:\n                return 1\n            \n            res = 0\n            for i in range(max(0, target - f), target):\n                if (level-1, i) in memo:\n                    res += memo[(level-1, i)]\n                else:\n                    tmp = num_rolls_util(level - 1, i)\n                    memo[(level-1, i)] = tmp\n                    res += tmp\n\n            return res % (10 ** 9 + 7)\n        \n        return num_rolls_util(d, target)\n    \n    # O(d * f * target) iterative\n#     def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n#         mod = 10 ** 9 + 7\n#         dp = [[0] * (target + 1) for _ in range(d+1)]\n#         dp[0][0] = 1\n        \n#         for i in range(1, d+1):\n#             for j in range(1, min(target, i * f) + 1):\n#                 for k in range(1, min(j, f) + 1):\n#                     dp[i][j] += dp[i-1][j-k] % mod\n        \n#         return dp[d][target] % mod        \n    \n    # def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n    #     # row: target value, col: number of dices\n    #     dp: List[List[int]] = [[0] * (d + 1) for _ in range(target + 1)]\n    #     for i in range(1, f + 1):  # initialize first col\n    #         if i <= target:\n    #             dp[i][1] = 1\n    #         else:\n    #             break\n    #     for j in range(2, d + 1):  # populate rest of dp matrix\n    #         for i in range(j, target + 1):\n    #             dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] - dp[i - min(i - 1, f) - 1][j - 1]  # line *\n    #     return dp[target][d] % (10**9 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d, f, target):\n        '''\n        :type d: int\n        :type f: int\n        :type target: int\n        :rtype: int\n        '''\n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        dp[0][0] = 1\n        mod = 10**9+7\n        for i in range(d+1):\n            for t in range(1, target+1):\n                for val in range(1, min(f, t)+1):\n                    dp[i][t] = (dp[i][t] + dp[i-1][t-val]) % mod\n        return dp[d][target]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # key = (num_rolls, target); value = (num_combinations)\n        memo = {}\n        def num_rolls_recur(d, target):\n            key = (d, target)\n            if key in memo:\n                return memo[key]\n            if target < 0:\n                return 0\n            if d == 0:\n                if target == 0:\n                    return 1\n                return 0\n            num_ways = 0\n            for i in range(1, f + 1):\n                num_ways = (num_ways + num_rolls_recur(d - 1, target - i)) % (pow(10, 9) + 7)\n            memo[key] = num_ways\n            return num_ways\n        return num_rolls_recur(d, target)", "class Solution:\n    def helper(self, d, f, target, dp):\n        if d == 0:\n            return 1 if target == 0 else 0\n        if (target, d) in dp:\n            # use cache | memoization\n            return dp[(target, d)]\n        for i in range(1, f + 1):\n            # we are branching dp into all of the sub cases\n            # sub cases are additive\n            dp[(target, d)] += self.helper(d - 1, f, target - i, dp)\n        return dp[(target, d)]\n        \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = Counter()\n        return self.helper(d, f, target, dp) % (pow(10, 9) + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp=[[0 for _ in range(target+1)] for _ in range(d+1)]\n        for i in range(1,min(f+1, target+1)):\n            dp[1][i]=1\n        for i in range(1, d+1):\n            for j in range(2, target+1):\n                for k in range(1,f+1):\n                    if j-k>=0:\n                        dp[i][j]+=dp[i-1][j-k]\n        #print(dp)\n        return dp[-1][-1]%1000000007\n            \n", "class Solution:\n    # Top down solution for dice sim\n    def helper(self, d, f, target, dp):\n        if d == 0:\n            return 1 if target == 0 else 0\n        if (target, d) in dp:\n            # use cache | memoization\n            return dp[(target, d)]\n        for i in range(1, f + 1):\n            # we are branching dp into all of the sub cases\n            # sub cases are additive\n            dp[(target, d)] += self.helper(d - 1, f, target - i, dp)\n        return dp[(target, d)]\n        \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = Counter()\n        return self.helper(d, f, target, dp) % (pow(10, 9) + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target == d or target == d*f:\n            return 1\n        T = [0 for i in range(target+1)]\n        m = 10**9 + 7\n        T[0]=1\n        for i in range(0,d):\n            for j in range(target,-1,-1):\n                T[j] = 0\n                for k in range(1,f+1):\n                    if j>=k:\n                        T[j]+= T[j-k] % m\n                        T[j]%=m\n        \n        return T[target]\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10**9 + 7\n        dp = [[0]*d for i in range(target + 1)]\n        \n        for i in range(1, target + 1):\n            dp[i][0] = int(i <= f)\n                \n                   \n        \n        for dd in range(1, d):\n            for ff in range(1, f+1):\n                for i in range(target + 1):\n                    if(i+ff <= target):\n                        dp[i+ff][dd] = ( dp[i+ff][dd] + dp[i][dd-1] ) % mod\n                        \n            \n        return dp[-1][-1]", "MOD = 1000000007\n\nclass Solution:\n    dyn = {}\n    def _get_res(self, d,f,target):\n        if d == 1:\n            return 1 if 0 < target and target <= f else 0\n        if (d, f, target) in self.dyn:\n            return self.dyn[(d, f, target)]\n        res = 0\n        for i in range(1, f + 1):\n            res += self._get_res(d - 1, f, target - i)\n\n        self.dyn[(d, f, target)] = res \n        \n        return res\n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        return self._get_res(d, f, target) % MOD", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        MOD = (10 ** 9) + 7\n        # print(MOD)\n        \n        f = min(f, target)\n        \n        dp = [[0 for t in range(target + 1)] for r in range(d)]\n        \n        # initialize for first roll (using just one die)\n        for i in range(1, f+1):\n            dp[0][i] = 1\n        \n        \n        # with dp, number of states can be 1 - 1000\n        \n        # how many ways can I get from a to b in less than 7 rolls?\n        # how many ways can I get from 0 to target in less than d rolls?\n        \n        # with transition cost as # of dice: \n        \n        # fill table\n        # simulate number of ways using 2 dice, then 3, etc.\n        for r in range(1, d):\n            # for each possible running sum\n            for i in range(1, target + 1):\n                # check if this sum is reachable by some roll of the new die\n                for val in range(1, f+1):\n                    if i-val >= 0:\n                        # add the number of ways to get to the current sum from the\n                        # previous sum, use modulus at this point to reduce computation costs\n                        dp[r][i] = (dp[r-1][i-val] + dp[r][i]) % MOD\n\n        # return the number of ways to reach target, using ALL dice\n        return dp[-1][target]\n        \n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        maxAmount = 10**9 + 7\n        \n        '''\n        dp[d][v] = dp[d-1][v-1] + dp[d-1][v-2] + ... + dp[d-1][v-f]\n        '''\n        if target < 1 or d * f < target:\n            return 0\n        \n        dpPrev = [(i, 1) for i in range(1, f+1)]\n        for roundNo in range(2, d+1):\n            numWays = defaultdict(int)\n            for i, v in dpPrev:\n                for num in range(1, f+1):\n                    numWays[i + num] += v\n            dpPrev = []\n            for k in numWays:\n                dpPrev.append((k, numWays[k]))\n        \n        for pair in dpPrev:\n            if pair[0] == target:\n                return pair[1] % maxAmount\n        \n        return 0                    \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10**9 + 7\n        dp = [[0] * (target + 1) for _ in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1, d+1):\n            for j in range(i, target+1):\n                \n                #dp[i][j] = dp[i-1][j]\n                for k in range(1, min(j, f)+1):\n                    if 0 <= j - k:\n                        dp[i][j] += dp[i-1][j-k]\n                dp[i][j] %= mod\n                        \n        return dp[d][target] % mod\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        MOD = (10 ** 9) + 7\n        # ways to roll target with d dice:\n        # roll target - 1, -2, -3, .. , -f with d - 1 dice\n        f = min(target, f)\n        dp = [[0 for val in range(target+1)] for die in range(d)]\n        \n        for i in range(1, f+1):\n            dp[0][i] = 1\n            \n        for i in range(1, d):\n            for val in range(target+1):\n                for face in range(1, f+1):\n                    if val - face >= 0:\n                        dp[i][val] = (dp[i-1][val-face] + dp[i][val]) % MOD\n        return dp[-1][target]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10**9+7\n        dp = [[0 for i in range(target+1)] for j in range(d+1)]\n        \n        dp[1] = [0] + [1 for i in range(f)] + [0 for i in range(target-f)]\n        \n        for i in range(1, d+1):\n            if i==1 or i==0:\n                continue\n            for j in range(1, target+1):\n                for k in range(1, f+1):\n                    if j-k > 0:\n                        dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % mod\n                        #dp[i][j] = (dp[i][j] + dp[i-1][j-k])\n        \n        #print(dp)\n        return dp[-1][-1]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [0] * (target+1)\n        dp[0] = 1\n        for i in range(1, d+1):\n            temp = [0]\n            # iterate each tot from 1 to target\n            for j in range(1, target+1):\n                # k is each face \n                x = sum(dp[j-k] if k <= min(j, f) else 0 for k in range(1, f+1))\n                temp.append(x)\n            # print(temp)\n            dp = temp\n\n        return dp[target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        \n        for dCand in range(1,d+1):\n            for targetCand in range(1,target+1):\n                if dCand == 1:\n                    dp[dCand][targetCand] = 1 if targetCand <= f else 0\n                    continue\n                allCombos = 0\n                for option in range(1,f+1):\n                    allCombos += dp[dCand-1][max(0,targetCand-option)]\n                dp[dCand][targetCand] = allCombos % (10 ** 9 + 7)\n        return dp[d][target]\n                \n        \n        \n        '''\n        dp[d][t]:\n            for each side:\n                smallerAns = dp[d-1][target-side]\n            dp[d][f] = sum of smaller answers\n        \n        base case:\n            dp[1][t] = 1 if t <= f, 0 otherwise\n            dp[d][<=0] = 0\n        '''\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        modu = 10**9+7\n        dp = [[0]*d for i in range(target + 1)]\n        for i in range(1, target + 1):\n            dp[i][0] = int(i <= f)\n            \n            \n        for dd in range(1, d):\n            for ff in range(1, f+1):\n                for i in range(target + 1):\n                    if(i+ff <= target):\n                        dp[i+ff][dd] = ( dp[i+ff][dd] + dp[i][dd-1]) % modu\n                        \n        return dp[-1][-1]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for j in range(target + 1)] for i in range(d + 1)]\n        dp[0][0] = 1\n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                for val in range(1, f + 1):\n                    if j - val >= 0:\n                        dp[i][j] = (dp[i][j] + dp[i - 1][j - val]) % (10 ** 9 + 7)\n        return dp[-1][-1] % (10 ** 9 + 7)\n        \n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        # target < d -> impossible \n        \n        # target > f*d -> impossible \n        def auxNumRolls(d, f, target, memoization):\n            if target < d or target > d*f:\n                return 0\n\n            # one die condition: only one possibility targe == die roll\n            if d == 1:\n                return 1\n\n            ans = 0\n            for i in range(1, f+1):\n                if (d-1, target-i) not in memoization:\n                    memoization[(d-1, target-i)] = auxNumRolls(d-1, f, target-i, memoization)\n                ans += memoization[(d-1, target-i)]\n            return ans\n        \n        \n        return auxNumRolls(d, f, target, {})%(10**9 + 7)\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10**9 + 7\n        state = [ 1 ] + [ 0 ] * ( target )\n        for i in range( d ) :\n            for j in range( target , -1 , -1 ) :\n                state[ j ] = 0\n                for k in range( 1 , min( f , j ) + 1 ) :\n                    state[ j ] += state[ j - k ]\n                    state[ j ] %= mod\n        return state[-1]\n#Sanyam Rajpal\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp = [[0] * (target+1) for _ in range(d)] # dp[i][j]: solution for target j with i + 1 dices\n        BASE = 10**9 + 7\n        for j in range(1, min(f, target)+1):\n            dp[0][j] = 1\n        for i in range(1, d):\n            for j in range(target+1):\n                for k in range(1, f+1):\n                    if k >= j: break\n                    dp[i][j] += dp[i-1][j-k] % BASE\n        \n        return dp[d-1][target] % BASE\n            \n", "# DP, either recursion or iteration works (recursion is faster than iteration, O(dt) vs. O(dft))\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = [[0] * (target + 1) for _ in range(d + 1)]\n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                if i == 1:\n                    if 1 <=j <= f:\n                        memo[i][j] = 1\n                    continue\n                for t in range(1, f+1):\n                    if j >= t:\n                        memo[i][j] += memo[i-1][j-t]\n        return memo[d][target] % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # NRT(d, f, t) = (sum over f' = {1, 2, ..., f}) numRollsToTarget(d - 1, f, t - f')\n        \n        dp = [] # dice x target\n        mod = math.pow(10, 9) + 7\n        \n        for _ in range(d + 1):\n            dp.append((target + 1) * [0])\n            \n        for i in range(target + 1):\n            dp[0][i] = 0\n            \n        for i in range(d + 1):\n            dp[i][0] = 0\n            \n        for i in range(min(f, target)):\n            dp[1][i + 1] = 1\n        \n        for i in range(2, d + 1):\n            for j in range(1, target + 1):\n                for roll in range(1, f + 1):\n                    if (j - roll >= 0):\n                        dp[i][j] = ((dp[i][j] % mod) + (dp[i - 1][j - roll] % mod)) % mod\n                        \n        return int(dp[d][target])", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        a = [[0] * (d+1) for _ in range(target+1)]\n        a[0][0] = 1\n        for i in range(1, target+1):\n            for j in range(1, d+1):\n                for k in range(1, f+1):\n                    if i >= k and j >= 1:\n                        a[i][j] =  (a[i][j] + a[i-k][j-1]) % (10**9+7)\n        return a[target][d]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = int(1e9) + 7\n        \n        dp = [[0 for _ in range(d + 1)] for _ in range(target + 1)]\n        for i in range(1, min(target + 1, f + 1)):\n            dp[i][1] = 1\n            \n        for i in range(2, target + 1):\n            for j in range(2, d + 1):\n                for k in range(1, min(f + 1, i + 1)):\n                    dp[i][j] += dp[i - k][j - 1]\n            \n        return dp[target][d] % mod", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d == 0:\n            return 0\n        \n        dp = [[0 for i in range(target + 1)] for i in range(d + 1)]\n        \n        for i in range(1, min(f + 1, target + 1)):\n            dp[1][i] = 1\n        \n        for i in range(2, d + 1):\n            for j in range(1, target + 1):\n                for k in range(1, f + 1):\n                    if j - k >= 0:\n                        dp[i][j] += dp[i - 1][j - k]\n                        \n                        if dp[i][j] >= 1000000007:\n                            dp[i][j] -= 1000000007\n        \n        return dp[d][target]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        if d*f < target or d > target:\n            return 0\n        \n        prev = {0:1}\n        \n        for x in range(d):\n            curr = {}\n            for y in range(1,f+1):\n                \n                for prev_sum,count in list(prev.items()):\n                    curr_sum = prev_sum+y\n                    if curr_sum <= target:\n                        curr[curr_sum] = curr.get(curr_sum,0)+count\n            prev = curr\n            # print(prev)\n        return prev[target]%(10**9+7) if target in prev else 0\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        DP = [[0]*(target+1) for _ in range(d+1)]\n        \n        for i in range(f+1):\n            if i <= target:\n                DP[1][i] = 1\n        if d == 1 :\n            return DP[d][target]\n        \n        for j in range(2,d+1):\n            for i in range(1,target+1):\n                for val in range(1,f+1):\n                    if 0< i-val <len(DP[j]):\n                        DP[j][i] += DP[j-1][i-val]\n        # print(DP)\n        return DP[d][target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10**9 + 7\n        # dp[i][j] use i dices to get target\n        dp = [[0]* (target+1) for _ in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1, d+1):\n            for j in range(target+1):\n                for k in range(1, f+1):\n                    if j >= k:\n                        dp[i][j] += dp[i-1][j-k]\n                        dp[i][j] %= mod\n        return dp[d][target]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, n: int) -> int:\n        mod = 10**9 + 7\n        dp = [0 for i in range(n+1)]\n        dp[0] = 1\n        temp = [0 for i in range(n+1)]\n        lol = [0 for i in range(n+1)]\n        for i in range(1,d+1):\n\n            for j in range(i,n+1):\n                for k in range(1,min(f+1,j+1)):\n                    temp[j]+=dp[j-k]\n                    temp[j] = temp[j]%mod\n            dp = temp.copy()\n            temp = lol.copy()\n        # print(dp)\n        return dp[-1]", "class Solution:\n\n            \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 1000000000+7\n        dp =[[0 for i in range(target+1)] for j in range(d)]\n        for i in range(d):\n            for j in range(target+1):\n                if i == 0:\n                    dp[i][j] = 1 if j>=1 and j<=f else 0\n                else:\n                    for l in range(1,f+1):\n                        if j-l>0:\n                            dp[i][j]+=dp[i-1][j-l]\n                            dp[i][j]%=mod\n        return dp [d-1][target] % mod\n", "class Solution:\n    '''\n    DP formula:\n    calc(d, target) = calc(d-1, target - 1) + calc(d-1, target - 2) + ... + calc(d-1, target - f)\n    example:\n    d = 2, target = 7, f = 6\n    calc(1, 1) = 1  -> one way to get 1 out of one 6 faced dice\n    calc(1, 2) = 1  -> one way to get 2 out of one 6 faced dice\n    calc(1, 3) = 1  -> one way to get 3 out of one 6 faced dice\n    ...\n    calc(1, 6) = 1 -> one way to get 6 out of one 6 faced dice\n    calc(1, 7) = 0 -> NO way to get 7 from one 6 faced dice\n    similarly, no way to get value > f using just one dice\n\n    calc(2, 1) = 0 -> 2 dice, target 1. impossible to get 1 using 2 six faced dice.\n    calc(2, 2) = 1 -> calc(1, 1) = 1. ways getting 2 out of 2 dice is similar to getting 1 out of 1 dice\n    calc(2, 3) = calc(1, 2) + calc(1, 1) = 1 + 1 = 2\n                 ways of getting 3 out of 2 dice meaning, ways of getting 2 using one dice [calc(1, 2)] \n                 and getting 1 from other dice [calc(1, 1)]\n    calc(2, 6) = calc(1, 1) + calc(1, 2) + calc(1, 3) + calc(1, 4) + calc(1, 5) + calc(1, 6)\n                ways to get 1 out of 1 dice then getting 5 from second dice +\n                ways to get 2 from first dice and then getting 4 from second dice +\n                ways to get 3 from first dice and getting 3 from second dice +\n                ways to get 4 from first dice and getting 2 from second dice +\n                ways to get 5 from first dice and getting 1 from second dice\n    '''\n    def numRollsToTarget(self, d, f, target):\n        mod_v = 10 ** 9 + 7 \n        dp = [[0] * (target + 1) for _ in range(d+1)]\n\n        for i in range(1, f+1):\n            if i > target:\n                break\n            #print(i)\n            dp[1][i] = 1\n        #print(dp)\n        for i in range(2, d+1):\n            for j in range(i, target+1):\n                for k in range(1, f+1):\n                    if j - k >= 0:\n                        dp[i][j] += dp[i-1][j-k]\n                        dp[i][j] %= mod_v\n                    else:\n                        break\n        #print(dp)\n        return dp[d][target]\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[None for _ in range(target+1)] for _ in range(d+1)]\n        \n        for dCand in range(d+1):\n            for targetCand in range(target+1):\n                if targetCand == 0 or dCand == 0:\n                    dp[dCand][targetCand] = 0\n                    continue\n                if dCand == 1:\n                    dp[dCand][targetCand] = 1 if targetCand <= f else 0\n                    continue\n                allCombos = 0\n                for option in range(1,f+1):\n                    allCombos += dp[dCand-1][max(0,targetCand-option)]\n                    allCombos %= (10 ** 9 + 7)\n                dp[dCand][targetCand] = allCombos\n        return dp[d][target]\n                \n        \n        \n        '''\n        dp[d][t]:\n            for each face:\n                smallerAns = dp[d-1][target-face]\n            dp[d][f] = sum of smaller answers\n        \n        base case:\n            dp[1][t] = 1 if t <= f, 0 otherwise\n            dp[d][<=0] = 0\n        '''\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        opt = [[0 for i in range(target+1)] for x in range(d)]\n        \n        for i in range(1,target+1):\n            if (i <= f):\n                opt[0][i] = 1\n                \n        for i in range(1,d):\n            for j in range(1, target+1):\n                for h in range(1,f+1):\n                    if (j-h > -1):\n                        opt[i][j] += opt[i-1][j-h]\n        \n        return opt[d-1][target] % (10**9 + 7)\n", "class Solution(object):\n   def numRollsToTarget(self, d, f, t):\n      mod = 1000000000+7\n      dp =[[0 for i in range(t+1)] for j in range(d)]\n      for i in range(d):\n         for j in range(t+1):\n            if i == 0:\n               dp[i][j] = 1 if j>=1 and j<=f else 0\n            else:\n               for l in range(1,f+1):\n                  if j-l>0:\n                     dp[i][j]+=dp[i-1][j-l]\n                     dp[i][j]%=mod\n      return dp [d-1][t] % mod\n", "import itertools\n\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n      mod = 1000000000+7\n      dp =[[0 for i in range(target+1)] for j in range(d)]\n      for i in range(d):\n         for j in range(target+1):\n            if i == 0:\n               dp[i][j] = 1 if j>=1 and j<=f else 0\n            else:\n               for l in range(1,f+1):\n                  if j-l>0:\n                     dp[i][j]+=dp[i-1][j-l]\n                     dp[i][j]%=mod\n      return dp [d-1][target] % mod", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d * f < target or d > target:\n            return 0\n        \n        if d == 1:\n            if target <=f:\n                return 1\n            else:\n                return 0\n        \n        M = 10**9 + 7\n        \n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        \n        dp[0][0] = 1\n        \n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                \n                if j == 1:\n                    dp[i][j] = dp[i - 1][0] \n                elif j <= f:\n                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]                \n                else:\n                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1] - dp[i - 1][j -f - 1])\n                    \n        return dp[d][target] % M", "class Solution:\n    # Recursive memoized solution\n#     def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n#         memo = {}\n#         def num_rolls_util(level, target):\n#             if level * f < target or target < level:\n#                 return 0\n#             if level == 0:\n#                 return 1\n            \n#             res = 0\n#             for i in range(max(0, target - f), target):\n#                 if (level-1, i) in memo:\n#                     res += memo[(level-1, i)]\n#                 else:\n#                     tmp = num_rolls_util(level - 1, i)\n#                     memo[(level-1, i)] = tmp\n#                     res += tmp\n\n#             return res % (10 ** 9 + 7)\n        \n#         return num_rolls_util(d, target)\n    \n    # O(d * f * target) iterative\n#     def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n#         mod = 10 ** 9 + 7\n#         dp = [[0] * (target + 1) for _ in range(d+1)]\n#         dp[0][0] = 1\n        \n#         for i in range(1, d+1):\n#             for j in range(1, min(target, i * f) + 1):\n#                 for k in range(1, min(j, f) + 1):\n#                     dp[i][j] += dp[i-1][j-k] % mod\n        \n#         return dp[d][target] % mod        \n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # row: target value, col: number of dices\n        dp: List[List[int]] = [[0] * (d + 1) for _ in range(target + 1)]\n        for i in range(1, f + 1):  # initialize first col\n            if i <= target:\n                dp[i][1] = 1\n            else:\n                break\n        for j in range(2, d + 1):  # populate rest of dp matrix\n            for i in range(j, target + 1):\n                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] - dp[i - min(i - 1, f) - 1][j - 1]  # line *\n        return dp[target][d] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, t: int) -> int:\n      mod = 1000000000+7\n      dp =[[0 for i in range(t+1)] for j in range(d)]\n      for i in range(d):\n         for j in range(t+1):\n            if i == 0:\n               dp[i][j] = 1 if j>=1 and j<=f else 0\n            else:\n               for l in range(1,f+1):\n                  if j-l>0:\n                     dp[i][j]+=dp[i-1][j-l]\n                     dp[i][j]%=mod\n      return dp [d-1][t] % mod", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n           \n        mod = int(10**9 + 7)\n        dp = [[0] * (target+1) for _ in range(d+1)] \n        for j in range(1, min(f+1, target+1)): dp[1][j] = 1\n        for i in range(2, d+1):\n            for j in range(1, target+1):\n                for k in range(1, f+1):\n                    if j - k >= 0: dp[i][j] += dp[i-1][j-k]\n                dp[i][j] %= mod        \n        return dp[-1][-1] \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        '''\n        d*f = total possible roll outcomes\n        \n        \n        d=2 f=6 target=7\n        \n        1+6 2+5 3+4 4+3 5+2 6+1\n        \n            0 1 2 3 4 5 6 7\n            0 1 1 1 1 1 1 0\n            0 0 1 2 3 4 5 6\n        dp[d][i] += dp[d-1][i-j] when j = 1...6 and i >= j\n        \n        '''\n        \n        dp = [[ 0 for _ in range(target+1)] for _ in range(d)]\n        \n        # initialize the first row with up to f\n        for i in range(1, min(f+1, target+1)): dp[0][i] = 1\n        \n        for i in range(1, d):\n            for j in range(1, target+1):\n                for k in range(1, f+1):\n                    if j-k >= 0:\n                        dp[i][j] += dp[i-1][j-k]\n                        dp[i][j] %= (10**9)+7\n                    \n        # print(dp)\n        return dp[d-1][target]\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        \n        for dCand in range(1,d+1):\n            for targetCand in range(1,target+1):\n                if dCand == 1:\n                    dp[dCand][targetCand] = 1 if targetCand <= f else 0\n                    continue\n                allCombos = 0\n                for option in range(1,f+1):\n                    allCombos += dp[dCand-1][max(0,targetCand-option)]\n                    allCombos %= (10 ** 9 + 7)\n                dp[dCand][targetCand] = allCombos\n        return dp[d][target]\n                \n        \n        \n        '''\n        dp[d][t]:\n            for each side:\n                smallerAns = dp[d-1][target-side]\n            dp[d][f] = sum of smaller answers\n        \n        base case:\n            dp[1][t] = 1 if t <= f, 0 otherwise\n            dp[d][<=0] = 0\n        '''\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for i in range(target+1)] for j in range(d+1)]\n        for i in range(1,d+1):\n            for j in range(1,target+1):\n                if i == 1:\n                    for k in range(1,min(f+1, target+1)):\n                        dp[i][k] = 1\n                else:\n                    num_permutations = 0\n                    for k in range(1,f+1):\n                        if j-k >= 0:\n                            num_permutations += dp[i-1][j-k]\n                    dp[i][j] = num_permutations\n        return int(dp[d][target] % (10**9+7))", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[None for _ in range(d+1)] for _ in range(target+2)]\n        for i in range(target+2):\n            dp[i][d] = 0\n        dp[target][d] = 1\n        for i in range(d+1):\n            dp[target+1][i] = 0\n        for i in range(target, -1, -1):\n            for j in range(d-1, -1, -1):\n                s = 0\n                for k in range(1, f+1):\n                    s+= dp[min(i+k, target+1)][j+1] % 1000000007\n                dp[i][j] = s\n        return dp[0][0] % 1000000007\n", "class Solution(object):\n   def numRollsToTarget(self, d, f, t):\n      mod = 1000000000+7\n      dp =[[0 for i in range(t+1)] for j in range(d)]\n      for i in range(d):\n         for j in range(t+1):\n            if i == 0:\n               dp[i][j] = 1 if j>=1 and j<=f else 0\n            else:\n               for l in range(1,f+1):\n                  if j-l>0:\n                     dp[i][j]+=dp[i-1][j-l]\n                     dp[i][j]%=mod\n      return dp [d-1][t] % mod\nob = Solution()\nprint(ob.numRollsToTarget(2,6,7))", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        MOD = 1000000007\n        dp = [[0] * 1001 for _ in range(31)]\n        mint = min(f, target)\n        targetMax = d*f\n        for i in range(1, mint+1):\n            dp[1][i] = 1\n        \n        for i in range(2,d+1):\n            for j in range(i, targetMax+1):\n                for k in range(1, min(j, f)+1):\n                    dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % MOD\n        return dp[d][target]\n\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, s: int) -> int:\n        mem = [[0 for _ in range(s + 1)] for _ in range(d + 1)]\n        mem[0][0] = 1\n        \n        for i in range(1,d + 1):\n            for j in range(1,s + 1):\n                mem[i][j] = mem[i][j - 1] + mem[i - 1][j - 1]\n                if j - f - 1 >= 0:\n                    mem[i][j] -= mem[i - 1][j - f - 1]\n                    \n        return mem[-1][-1] % (10 ** 9 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        m = pow(10,9)+7\n        T = [[0 for i in range(max(target+1, f+1))] for i in range(d)]\n        for i in range(f):\n            T[0][i+1] = 1\n        for i in range(1,d):\n            for j in range(1,target+1):\n                for k in range(1,f+1):\n                    if j-k>0:\n                        T[i][j] += T[i-1][j-k]\n                        T[i][j] = T[i][j]%m\n            #print(T)\n        return T[d-1][target]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod=10**9 + 7\n        dp=[[0 for i in range(target+1)] for j in range (d)]\n        for i in range(d):\n            for j in range(target+1):\n                if i == 0:\n                    dp[i][j] = 1 if j>=1 and j<=f else 0\n                else:\n                    for l in range(1,f+1):\n                        if j-l>0:\n                            dp[i][j]+=dp[i-1][j-l]\n                            dp[i][j]%=mod\n        print(dp)\n        return dp[-1][-1]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(target + 1)] for _ in range(d + 1)]\n        dp[0][0] = 1\n        mod = 10 ** 9 + 7\n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                ff = 1\n                highest_die = min(j, f)\n                while ff <= highest_die:\n                    dp[i][j] += dp[i-1][j-ff]\n                    dp[i][j] %= mod\n                    ff += 1\n                    \n        return dp[d][target] % mod\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target == d or target == d*f:\n            return 1\n        T = [[0 for j in range(target+1)] for i in range(d+1)]\n        m = 10**9 + 7\n\n        T[0][0] = 1\n        for i in range(1,d+1):\n            T[i][0] = 0 \n            for j in range(1,target+1,1):\n                for k in range(1,f+1):\n                    if j>=k:\n                        T[i][j]+= T[i-1][j-k] % m\n                        T[i][j]%=m\n\n        return T[d][target] % m\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        t = target\n        mod = 1000000000+7\n        dp =[[0 for i in range(t+1)] for j in range(d)]\n        for i in range(d):\n            for j in range(t+1):\n                if i == 0:\n                    dp[i][j] = 1 if j>=1 and j<=f else 0\n                else:\n                    for l in range(1,f+1):\n                        if j-l>0:\n                            dp[i][j]+=dp[i-1][j-l]\n                            dp[i][j]%=mod\n        return dp [d-1][t] % mod", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp = [[0]+[0]*target for _ in range(d)]\n        \n        for i in range(d):\n            for j in range(1,target+1):\n                for k in range(1,f+1):\n                    if k>j: break\n                    if i==0: dp[i][j] = int(j==k)\n                    else: dp[i][j] += dp[i-1][j-k]\n                    if dp[i][j]>10**9: dp[i][j] = (dp[i][j]%(10**9))-(7*(dp[i][j]//(10**9)))\n        \n        return dp[-1][-1]", "class Solution:\n    \n    @lru_cache(maxsize=None)\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp = [[0]+[0]*target for _ in range(d)]\n        for i in range(d):\n            for j in range(1,target+1):\n                for k in range(1,f+1):\n                    if k>j: break\n                    if i==0: dp[i][j] = int(j==k)\n                    else: dp[i][j] += dp[i-1][j-k]\n                    if dp[i][j]>10**9: dp[i][j] = (dp[i][j]%(10**9))-(7*(dp[i][j]//(10**9)))\n        \n        return dp[-1][-1]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod=int(10**9+7)\n        dp=[[0 for i in range(d+1)] for j in range(target+1)]\n        dp[0][0]=1\n        for i in range(1,target+1):\n            for j in range(1,d+1):\n                for k in range(1,f+1):\n                    if i>=k:\n                        dp[i][j]+=(dp[i-k][j-1]%mod)\n                    dp[i][j]=dp[i][j]%mod\n        return dp[-1][-1]%mod", "class Solution:\n    def numRollsToTarget(self, d, f, target):\n        \n        if d == 0:\n            return 0\n        \n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        \n        for i in range(1, target+1):\n            dp[0][i] = 0\n        for j in range(1, d+1):\n            dp[j][0] = 0\n            \n        dp[0][0] = 1\n        \n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                for k in range(1, f+1):\n                    if j-k >= 0:\n                        dp[i][j] += dp[i-1][j-k]\n                        dp[i][j] %= ((10 ** 9) + 7)\n                        \n        return dp[d][target]\n                \n                \n#         def recursive(d, f, target):\n            \n#             if target == 0 and d == 0:\n#                 return 1\n            \n#             if target < 0 or d == 0:\n#                 return 0\n            \n#             if dp[d][target] != -1:\n#                 return dp[d][target]\n#             temp = 0\n#             for i in range(1, f+1):\n#                 temp += recursive(d - 1, f, target - i)\n                \n#             dp[d][target] =  temp\n#             return dp[d][target]\n\n#         return (recursive(d, f, target) % ((10 ** 9) + 7))\n", "from functools import lru_cache\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        if d*f < target:\n            return 0\n        \n        @lru_cache(maxsize = None)\n        def dfs(index, target):\n            if index == d:\n                if target == 0:\n                    return 1\n                return 0\n            \n            if target <= 0:\n                return 0\n            \n            ret = [0]*(f + 1)\n            for num in range(1,f+1):\n                ret[num] = dfs(index + 1, target - num)\n            \n            return sum(ret) % (10**9 + 7)\n        \n        return dfs(0, target)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        m = collections.defaultdict(int)\n        m[(0, 0)] = 0\n        for t in range(1, 1+f):\n            m[(1, t)] = 1\n        for i in range(1,1+d):\n            for j in range(1, 1+target):\n                for k in range(1, min(1+f, j)):\n                    m[(i,j)] += m[(i-1, j-k)]\n        return m[(d,target)]%(10**9+7)", "class Solution:\n    def helper(self, d, f, target, num_ways):\n        if d == 0:\n            if target == 0:\n                return 1\n            else:\n                return 0\n        \n        if (d, target) in num_ways:\n            return num_ways[(d, target)]\n        \n        for face in range(1, f+1):\n            num_ways[(d, target)] += self.helper(d-1, f, target - face, num_ways)\n            \n        return num_ways[(d, target)]\n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        num_ways = collections.defaultdict(int)\n        \n        self.helper(d, f, target, num_ways)\n        \n        return num_ways[(d, target)] % (1000000000 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[None for _ in range(d+1)] for _ in range(target+2)]\n        for i in range(target+2):\n            dp[i][d] = 0\n        dp[target][d] = 1\n        for i in range(d+1):\n            dp[target+1][i] = 0\n        for i in range(target, -1, -1):\n            for j in range(d-1, -1, -1):\n                s = 0\n                for k in range(1, f+1):\n                    s+= dp[min(i+k, target+1)][j+1] % 1000000007\n                dp[i][j] = s\n        return dp[0][0] % 1000000007\n            \n        \n        \n        \n        def solve(x, i):\n            if i == d:\n                if x == target:\n                    return 1\n                return 0\n            if x >= target:\n                return 0\n            s = 0\n            for j in range(1, f+1):\n                s+= solve(x+j, i+1) % 1000000007\n            return s\n        \n        return solve(0, 0) % 1000000007\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # initialization\n        f = min(target, f)\n        MOD = 10**9 + 7\n        dp = [[None for _ in range(target + 1)] for _ in range(d + 1)]\n        for i in range(1, f + 1):\n            dp[1][i] = 1\n            \n        # computing\n        for i in range(2, d + 1):\n            for j in range(1, target + 1):\n                dp[i][j] = 0\n                for k in range(1, f + 1):\n                    if j - k >= 1 and dp[i - 1][j - k] is not None:\n                        dp[i][j] += dp[i - 1][j - k]\n                        \n                dp[i][j] %= MOD\n                \n        return dp[d][target] if dp[d][target] is not None else 0", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        if target > f*d:\n            return 0\n        \n        @lru_cache(None)\n        def dp(target, f, d):\n            if target == 0 and d == 0:\n                return 1\n            \n            if target <= 0:\n                return 0\n            \n            count = 0\n            \n            for i in range(1, f+1):\n                count += dp(target - i, f, d-1)\n                count %= (10**9 + 7)\n                \n            return count\n    \n        return int(dp(target, f, d) % (10**9 + 7))\n            \n\n# # ############\n# f = 3\n# ans = [1,1,2],[1,2,1],[2,1,1]\n# count = 3\n# dp(3, 4)\n# d = 3\n# target = 4\n# i = 2\n# -------\n# dp(2, 2)\n# d = 2\n# target = 2\n# i = 1\n# ------\n# dp(1, 1)\n# d = 1\n# target = 1\n# i = 1\n# ------\n# dp(0, 0)\n# d = 0\n# target = 0\n# ------\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0] * (target + 1) for _ in range(d + 1)]\n        dp[0][0] = 1\n        \n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                for k in range(1, f + 1):\n                    if (j - k) < 0:\n                        break\n                    dp[i][j] += dp[i-1][j-k]\n                    dp[i][j]  = dp[i][j]%(10**9 + 7)\n        \n        return dp[-1][-1]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10**9 + 7\n        dp = [[0] * (target + 1) for _ in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                \n                #dp[i][j] = dp[i-1][j]\n                for k in range(1, f+1):\n                    if 0 <= j - k:\n                        dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % mod\n                \n                        \n        return dp[d][target]\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 1000000007\n        dp = [[0] * (d+1) for i in range(target+1)]\n        for tar in range(1, target+1):\n            if f >= tar:\n                dp[tar][1] = 1\n        for dice in range(2, d+1):\n            for tar in range(1, target+1):\n                for possVal in range(1, f+1):\n                    if tar - possVal >= 1:\n                        dp[tar][dice] = (dp[tar][dice] + dp[tar-possVal][dice-1]) % mod\n        print(dp)\n        return dp[-1][-1]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        if not d or not f or not target: return 0\n        \n        dp = [[0]*(target+1) for _ in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1,len(dp)):\n            for j in range(1,len(dp[0])):\n                k = 1\n                while k <= min(j,f):\n                    dp[i][j] += dp[i-1][j-k]\n                    k += 1\n                \n        return dp[-1][-1] % (10**9+7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        table=[[0]*(target+1) for i in range(d+1)]  \n      \n        for j in range(1,min(f+1,target+1)):  \n            table[1][j]=1\n          \n        for i in range(2,d+1): \n            for j in range(1,target+1): \n                for k in range(1,min(f+1,j)): \n                    table[i][j]+=table[i-1][j-k] \n     \n        return table[-1][-1] % 1000000007\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, s: int) -> int:\n        mem = [[0 for _ in range(s + 1)] for _ in range(d + 1)]\n        mem[0][0] = 1\n        for i in range(1,d + 1):\n            for j in range(1,s + 1):\n                mem[i][j] = mem[i][j - 1] + mem[i - 1][j - 1]\n                if j - f - 1 >= 0:\n                    mem[i][j] -= mem[i - 1][j - f - 1]\n        return mem[-1][-1] % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0] * (target + 1) for _ in range(d + 1)]\n        MOD = 10 ** 9 + 7\n        dp[0][0] = 1\n\n        # for j in range(target + 1):\n        #     dp[0][j] = 1\n\n        for j in range(1, d + 1):\n            for i in range(1, target + 1):\n                for k in range(1, f + 1):\n                    if i - k < 0:\n                        break\n                    dp[j][i] = (dp[j][i] + dp[j - 1][i - k]) % MOD\n\n        return dp[d][target]\n\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for i in range(target+1)] for j in range(d)]\n        print(dp)\n        for i in range(f):\n            if i + 1 <= target:\n                dp[0][i+1] = 1\n                \n        for i in range(1,d):\n            for j in range(1,target+1):\n                #start with k = 1, accumulate all possible number sum before f\n                #if this dice presents 1, then the sum up to the current j is related to the result in j-k, the previous sum in i-1 try.\n                \n                k = 1\n                while j-k > 0 and k <= f:\n                    \n                    dp[i][j] += dp[i-1][j-k]\n                    k+=1\n                    \n        return dp[-1][-1] % (1000000000+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # time O(dft), space O(dt) --> optimize space O(t)\n        dp = [[0] * (target + 1) for _ in range(d + 1)]\n        dp[0][0] = 1\n        \n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                for k in range(1, f + 1):\n                    if (j - k) < 0:\n                        break\n                    dp[i][j] += dp[i-1][j-k]\n                    dp[i][j]  = dp[i][j]%(10**9 + 7)\n        \n        return dp[-1][-1]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp=[[0]*(target+1) for _ in range(d+1)]\n        md=pow(10,9)+7\n        dp[0][0]=1\n        for trial in range(1,d+1):\n            for i in range(target):\n                for face in range(1,f+1):\n                    if i+face<=target:\n                        dp[trial][i+face]+=dp[trial-1][i]\n                        dp[trial][i+face]%=md\n        \n        return dp[-1][target]\n            \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(d+1)] for _ in range(target+1)]\n        if target < d: return 0\n        for i in range(2,d+1): dp[1][i] = 0\n        for i in range(1,min(f+1,target+1)): dp[i][1] = 1            \n        for D in range(2,d+1):\n            for s in range(1,target+1):\n                for k in range(1,f+1):\n                    dp[s][D] += dp[s-k][D-1] if s-k >= 1 and D > 1  else 0\n                    dp[s][D] = dp[s][D]%1000000007\n        return dp[target][d]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp = [[0] * (target+1) for i in range(d+1)]\n        \n      \n       \n            \n        # for i in range(d+1):\n        #     if \n        #     dp[1][0] = 1\n        \n        dp[0][0] = 1\n        \n        for i in range(d+1):\n            for j in range(target+1):\n                \n                for k in range(1,f+1):\n                    if j-k>=0:\n                        \n                        dp[i][j] += dp[i-1][j-k]\n                    \n                   \n                    \n        return dp[d][target] % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp=[[0]*(target+1) for i in range(d+1)]\n        dp[0][0]=True\n        \n        for i in range(1,d+1):\n            for j in range(1,target+1):\n                k=1\n                while k<=min(j,f):\n                    dp[i][j]+=dp[i-1][j-k]\n                    k+=1\n        \n        mod=10**9+7\n        return dp[-1][-1]%mod", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dice = [k for k in range(1,f+1)]\n        dp = [[0 for _ in range(d+1)]for _ in range(target+1)]\n        \n        def numRolls(d,f,target):\n            for j in range(1,min(f+1,target+1)): dp[j][1] = 1\n            for i in range(2,d+1):\n                for j in range(1,target+1):\n                    for new_t in list(map(lambda k: j-k,dice)):\n                        if new_t >= 0 :\n                            dp[j][i] += dp[new_t][i-1]\n                        dp[j][i] \n            return dp[target][d]% (10**9 + 7)\n        \n                        \n        return numRolls(d,f,target)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp=[[0]*(target+1) for i in range(d+1)]\n        \n        dp[0][0]=1\n        mod=10**9+7\n        for i in range(1,d+1):\n            for j in range(1,target+1):\n                k=1\n                while k<=min(j,f):\n                    dp[i][j]+=dp[i-1][j-k]\n                    k+=1\n        \n        return dp[-1][-1]%mod", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10 ** 9 + 7\n        if target > d * f:\n            return 0\n        \n        dp = [[0 for j in range(target+1)] for i in range(d+1)]\n        for j in range(1, min(f, target)+1):\n            dp[1][j] = 1\n        for i in range(2, d+1):\n            for j in range(1, target+1):\n                for k in range(max(1, j-f), j):\n                    dp[i][j] += dp[i-1][k]\n        return dp[d][target] % mod", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        mod = 10 ** 9 + 7\n        dp = [[0 for j in range(target + 1)] for i in range(d + 1)]\n        dp[0][0] = 1\n        for i in range(d):\n            for ff in range(1, f + 1):\n                for sm in range(target):\n                    if sm + ff <= target:\n                        dp[i + 1][sm + ff] += dp[i][sm]\n                        dp[i + 1][sm + ff] %= mod\n        return dp[d][target]\n\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0]*(target+1) for _ in range(d+1)]\n        dp[0][0] = 1\n        \n        for i in range(1, d+1):\n            for j in range(target, i-1, -1):\n                for k in range(1, f+1):\n                    if j-k<0: break\n                    \n                    dp[i][j] += dp[i-1][j-k]\n        # print(dp)\n        return dp[d][target]%(10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp=[[0]*(target+1) for i in range(d+1)]\n        \n        dp[0][0]=1\n        \n        for i in range(1,d+1):\n            for j in range(1,(target+1)):\n                k =1\n                while k <= min(f,j):\n                    dp[i][j] = (dp[i][j] + dp[i-1][j-k])\n                    k +=1\n        return dp[d][target]% (10**9 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10**9 + 7\n        dp = [[0 for j in range(target + 1)] for i in range(d + 1)]\n        dp[0][0] = 1\n        for i in range(1, d + 1):\n            for ff in range(1, f + 1):\n                for sm in range(target):\n                    if sm + ff <= target:\n                        dp[i][sm + ff] += dp[i - 1][sm]\n                        dp[i][sm + ff] %= mod\n        return dp[d][target]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[None for _ in range(d+1)] for _ in range(target+2)]\n        for i in range(target+2):\n            dp[i][d] = 0\n        dp[target][d] = 1\n        for i in range(d+1):\n            dp[target+1][i] = 0\n        for i in range(target, -1, -1):\n            for j in range(d-1, -1, -1):\n                dp[i][j] = 0\n                for k in range(1, f+1):\n                    dp[i][j]+= dp[min(i+k, target+1)][j+1] % 1000000007\n        return dp[0][0] % 1000000007\n", "MODULE = 10**9 + 7\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target < d:\n            return 0\n        #\u7528 j \u4e2a\u6570\u6765\u51d1\u51fa\u548c\u4e3a j \u7684\u5168\u90e8\u7ec4\u5408\u53ef\u80fd\u6027\n        dp = [[0] * (target + 1) for _ in range(d + 1)]\n        for i in range(1, f + 1):\n            if i > target:\n                break\n            dp[1][i] = 1\n            \n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                for face in range(1, f + 1):\n                    if j >= face:\n                        dp[i][j] = (dp[i][j] + dp[i - 1][j - face]) % MODULE\n        # print (dp)\n        return dp[d][target]\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp=[[0]*(target+1) for i in range(d+1)]\n        \n        dp[0][0]=1\n        \n        for i in range(1,d+1):\n            for j in range(1,target+1):\n                k=1\n                while k<=min(j,f):\n                    dp[i][j]+=dp[i-1][j-k]\n                    k+=1\n        \n        mod=10**9+7\n        return dp[-1][-1]%mod", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp=[[0]*(target+1) for i in range(d+1)]\n        \n        dp[0][0]=1\n        \n        for i in range(1,d+1):\n            for j in range(1,target+1):\n                k=1\n                while k<=min(j,f):\n                    dp[i][j]+=dp[i-1][j-k]\n                    k+=1\n        \n        mod=10**9+7\n        return dp[-1][-1]%(mod)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(max(target+1,f+1))] for _ in range(d+1)]\n        for i in range(1,f+1):\n            dp[1][i] = 1\n        break_flag = False\n        for i in range(1,d):\n            break_flag = False\n            \n            for j in range(1,max(target+1,f+1)):\n                for n in range(1,f+1):\n                    if j+n <= max(target,f):\n                        dp[i+1][j+n] += dp[i][j] \n                    else:\n                        break\n                        break_flag = True\n                if break_flag:\n                    break\n                        \n                \n        return dp[d][target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, s: int) -> int:\n        mem = [[0 for _ in range(s + 1)] for _ in range(d + 1)]\n        mem[0][0] = 1\n        for i in range(1,d + 1):\n            for j in range(1,s + 1):\n                mem[i][j] = mem[i][j - 1] + mem[i - 1][j - 1]\n                if j - f - 1 >= 0:\n                    mem[i][j] -=  mem[i - 1][j - f - 1]\n                    \n        return mem[-1][-1] % (10 ** 9 + 7)\n                    \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(max(target+1,f+1))] for _ in range(d+1)]\n        for i in range(1,f+1):\n            dp[1][i] = 1\n        for i in range(1,d):\n            for j in range(1,max(target+1,f+1)):\n                for n in range(1,f+1):\n                    if j+n <= max(target,f):\n                        dp[i+1][j+n] += dp[i][j] \n                    else:\n                        break\n        return dp[d][target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0]*(target+1) for _ in range(d+1)]\n        dp[0][0] = 1\n        MOD = 10**9+7\n        \n        for i in range(d):\n            for j in range(target+1):\n                for k in range(1, f+1):\n                    if j+k<=target:\n                        dp[i+1][j+k] += dp[i][j]\n                        dp[i+1][j+k] %= MOD\n\n        return dp[d][target]\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10**9 + 7\n        dp = [ [ 0 for _ in range( target + 1 ) ] for _ in range( d + 1 ) ]\n        dp[ 0 ][ 0 ] = 1\n        for i in range( d ) :\n            for j in range( 1 , f + 1 ) :\n                for k in range( target ) :\n                    if k + j <= target :\n                        dp[ i + 1 ][ k + j ] += dp[ i ][ k ]\n                        dp[ i + 1 ][ k + j ] %= mod\n        return dp[-1][-1]\n#Sanyam Rajpal\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d == 0:\n            return 0\n        q = collections.deque([(i+1, 1) for i in range(f)])\n        visited = {(0,0): 1}\n        while(q):\n            s, di = q.popleft()\n            if (s, di) in visited:\n                continue\n            npath = sum(visited.get((s-i-1, di-1), 0) for i in range(f))\n            if (di==d):\n                if (s==target):\n                    return npath % (1000000007)\n                else:\n                    continue\n            visited[(s, di)] = npath\n            q += [(s+i+1, di+1) for i in range(f)]\n        return 0\n        \n            \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if not d or not f or not target: return 0\n        \n        dp = [[0]*(target+1) for _ in range(d+1)]\n        \n        dp[0][0] = 1\n        for i in range(1,len(dp)):\n            for j in range(1,len(dp[0])):\n                k=1\n                while k <= min(j,f):\n                    dp[i][j] += dp[i-1][j-k] % (10**9 + 7)\n                    k+=1\n                \n        \n        return dp[-1][-1] % (10**9 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0]*(target+1) for _ in range(d+1)]\n        dp[0][0] = 1\n        mod = 10**9 + 7\n        for i in range(1, d+1):\n            for j in range(1, target+1):\n                k = 1\n                while k <= min(j, f):\n                    dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % mod\n                    k += 1\n        return dp[d][target] % mod            \n", "from itertools import product\n\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for i in range(target + 1)] for j in range(d + 1)]\n        dp[0][0] = 1\n        mod = 10 ** 9 + 7\n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                k = 1\n                while k <= min(j, f):\n                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod\n                    k += 1\n        return dp[d][target] % mod\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10**9 + 7\n        dp = [[0 for j in range(target + 1)] for i in range(d + 1)]\n        dp[0][0] = 1  # * 1 way to make 0 with 0 dice\n        for i in range(d):\n            for ff in range(1, f + 1):\n                for sm in range(target):\n                    if sm + ff <= target:\n                        dp[i + 1][sm + ff] += dp[i][sm]\n                        dp[i + 1][sm + ff] %= mod\n                    else:\n                        break\n        return dp[d][target]\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for i in range(target + 1)] for j in range(d + 1)]\n        dp[0][0] = 1\n        mod = 10 ** 9 + 7\n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                k = 1\n                while k <= min(j, f):\n                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod\n                    k += 1\n        return dp[d][target] % mod", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        #dp, tree -> check which leaf has val = target \n        # recursion : memory overload\n        # ways of d dices with f faces to sum up to target = ways of d-1 dices to sum to target-1 + ways of d-1 dices to sum to target-2 +..\n        # rolls[d][target] \n        \n        rolls = []\n        for i in range(d+1):\n            rolls.append([0]*(target+1))\n        \n        for i in range(target+1):\n            rolls[0][i] = 0\n            \n        for i in range(d+1):\n            rolls[i][0] = 0\n            \n        for i in range(1,target+1):\n            if i<=f:\n                rolls[1][i] = 1\n        \n        for i in range(2,d+1):\n            for j in range(1, target+1):\n                k = 1\n                while(k<=f):\n                    if(j-k) < 0:\n                        break\n                    rolls[i][j] += rolls[i-1][j-k]\n                    k += 1\n        \n        #print(10**9)\n        return (rolls[d][target] %(10**9 + 7))", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # d = 5, f=3, target=11\n        # d=4, f=3, target=10 + d=4, f=3, target=9, d=4 f=3 target=9\n        def rec_find_target_sum(d, f, target):\n            if (d,f,target) in memo:\n                return memo[(d,f,target)]\n            if d == 0 or d*f < target or target <= 0:\n                return 0\n            if d == 1:\n                return 1\n            \n            possibs = 0\n            for face in range(f):\n                possibs += rec_find_target_sum(d-1, f, target-face-1)\n            memo[(d,f,target)] = possibs\n            return possibs\n        \n        memo = {}\n        return rec_find_target_sum(d, f, target) % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d,f,target):\n        dp = [[0]*(target+1) for _ in range(d+1)]\n        \n        dp[0][0] = 1\n        mod = 10**9 + 7\n        \n        for i in range(1 , d+1):\n            for j in range(1 , target+ 1):\n                k = 1 \n                while k <= min(f , j):\n                    dp[i][j] = (dp[i][j]  + dp[i-1][j-k])%mod\n                    k +=  1\n        return dp[d][target]\n         \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10 ** 9 + 7\n        dp = [[0 for j in range(target + 1)] for i in range(d + 1)]\n        dp[0][0] = 1\n        for i in range(d):\n            for ff in range(1, f + 1):\n                for sm in range(target):\n                    if sm + ff <= target:\n                        dp[i + 1][sm + ff] += dp[i][sm]\n                        dp[i + 1][sm + ff] %= mod\n        return dp[d][target]\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        dp = [[0 for i in range(target + 1)] for j in range(d + 1)]\n        dp[0][0] = 1\n        \n        \n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                k = 1\n                while k <= min(j, f):\n                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % (10 ** 9 + 7)\n                    k += 1\n        \n        return dp[d][target] % (10 ** 9 + 7)\n    \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10**9 + 7\n        dp = [[0] * (target + 1) for _ in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1, d+1):\n            for j in range(i, target+1):\n                \n                #dp[i][j] = dp[i-1][j]\n                for k in range(1, f+1):\n                    if 0 <= j - k:\n                        dp[i][j] += dp[i-1][j-k]\n                dp[i][j] %= mod\n                        \n        return dp[d][target] % mod\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for i in range(target + 1)] for j in range(d + 1)]\n        dp[0][0] = 1\n        mod = 10 ** 9 + 7\n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                k = 1\n                while k <= min(j, f):\n                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) \n                    k += 1\n        return dp[d][target] % mod", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dice = [k for k in range(1,f+1)]\n        dp = [[0 for _ in range(d+1)]for _ in range(target+1)]\n        \n        def numRolls(d,f,target):\n            for j in range(1,min(f+1,target+1)): dp[j][1] = 1\n            for i in range(2,d+1):\n                for j in range(1,target+1):\n                    for new_t in list([j-k for k in dice]):\n                        if new_t >= 0 :\n                            dp[j][i] += dp[new_t][i-1]\n                        dp[j][i] %= (10**9 + 7)\n            return dp[target][d]\n        \n                        \n        return numRolls(d,f,target)\n    \n    # def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n    #     if d*f < target: return 0        # Handle special case, it speed things up, but not necessary\n    #     elif d*f == target: return 1     # Handle special case, it speed things up, but not necessary\n    #     mod = int(10**9 + 7)\n    #     dp = [[0] * (target+1) for _ in range(d+1)] \n    #     for j in range(1, min(f+1, target+1)): dp[1][j] = 1\n    #     for i in range(2, d+1):\n    #         for j in range(1, target+1):\n    #             for k in range(1, f+1):\n    #                 if j - k >= 0: dp[i][j] += dp[i-1][j-k]\n    #             dp[i][j] %= mod        \n    #     return dp[-1][-1] \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # Dynamic programming on the number of dice?\n        # if i have n - 1 dice, and know the number of ways to get to all possible targets\n        # then i should be able to compute the number of way to get to a target with n dice\n        \n       # keep a vector of number of ways to get to targets between 1 and \\\"target\\\" for d = 1 etc\n    \n        dp = [[0 for i in range(target + 1)] for j in range(d + 1)]\n        dp[0][0] = 1\n        mod = 10 ** 9 + 7\n        for i in range(1, d + 1):\n            for j in range(1, target + 1):\n                k = 1\n                while k <= min(j, f):\n                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod\n                    k += 1\n        return dp[d][target] % mod\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        dp[0][0] = 1\n        mod = 10 **9 + 7\n        for i in range(1,len(dp)):\n            for j in range(1,len(dp[0])):\n                k = 1\n                while k <= min(j,f):\n                    dp[i][j] = (dp[i][j]+ dp[i-1][j-k]) % mod\n                    k += 1\n        return dp[-1][-1] % mod\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {} # num of ways for combo of [# of rolls, target]\n        def rollDice(d, target):\n            if target < 0 or target > f * d: # def 0 way\n                memo[d, target] = 0\n                return 0\n            if d == 0: # base case \n                return 0 if target > 0 else 1\n            if (d, target) in memo: # if already computed\n                return memo[d, target]\n            total = 0  # actual computation\n            for num in range(1, f + 1):\n                total += rollDice(d - 1, target - num) #dp based on previous roll \n            memo[d, target] = total\n            return total\n            \n        return rollDice(d, target) % (10**9 + 7)\n        \n        \n    # for each roll, f doesn't change, dp[d, target] = dp[d-1, target-1] + dp[d-1, target-2] + ... + dp[d-1, target-f]. That is, cur total # of steps is sum of total # of steps of all possible last steps (determined by # of faces last dice has)\n    # base case is when d is 0 (no roll left), target is 0, there is one way. If target > 0 and d is 0, there is no way. \n    # bcs for each layer we have, the num of operations for the same d value is timed by f, there's a lot of repetition value there. Therefore we use memoization\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        def helper(h, d, target):\n            # if target is too small or if it is out of range\n            if target <= 0 or target > (d * f):\n                return 0\n            if d == 1:\n                return 1        # no need to check if target is within reach; already done before\n            if (d, target) in h:\n                return h[(d, target)]        # directly access from hash table\n            res = 0\n            for i in range(1, f + 1):\n                res += helper(h, d - 1, target - i)       # check all possible combinations\n            h[(d, target)] = res\n            return h[(d, target)]\n        \n        h = {}\n        return helper(h, d, target) % (10 ** 9 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [1]+[0]*target\n        for i in range(d):\n            for j in range(target,-1,-1):\n                dp[j] = sum(dp[max(0,j-f):j])\n                \n        return dp[target] % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target < d or target > d * f:\n            return 0\n        if target > (d*(1+f)/2):\n            target = d * (1 + f) - target\n        dp = [0] * (target + 1) \n        for i in range(1, min(f, target) + 1):\n            dp[i] = 1\n        for i in range(2, d + 1):\n            new_dp = [0] * (target + 1)\n            for j in range(i, min(target, i * f) + 1):\n                new_dp[j] = new_dp[j - 1] + dp[j - 1]\n                if j - 1 > f:\n                    new_dp[j] -= dp[j - f - 1]\n            dp = new_dp\n\n        return dp[target] % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        def helper(h, d, target):\n            # if target is too small or if it is out of range\n            if target <= 0 or target > (d * f):\n                return 0\n            if d == 1:\n                return 1        # no need to check if target is within reach; already done before\n            if (d, target) in h:\n                return h[(d, target)]        # directly access from hash table\n            res = 0\n            for i in range(1, f + 1):\n                res += helper(h, d - 1, target - i)       # check all possible combinations\n            h[(d, target)] = res\n            return h[(d, target)]\n        \n        h = {}\n        return helper(h, d, target) % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d*f < target: return 0        # Handle special case, it speed things up, but not necessary\n        elif d*f == target: return 1     # Handle special case, it speed things up, but not necessary\n        mod = int(10**9 + 7)\n        dp = [[0] * (target+1) for _ in range(d+1)] \n        for j in range(1, min(f+1, target+1)): dp[1][j] = 1\n        for i in range(2, d+1):\n            for j in range(1, target+1):\n                for k in range(1, f+1):\n                    if j - k >= 0: dp[i][j] += dp[i-1][j-k]\n                dp[i][j] %= mod        \n        return dp[-1][-1] ", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # if d*f < target:\n        #     return 0\n        # elif d*f==target:\n        #     return 1\n        \n        faces = [i for i in range(1,f+1)]\n        cache = {}\n        def dfs(left,numDice):\n            re = 0\n            if (left,numDice) in cache:\n                return cache[(left,numDice)]\n            if left>f*(d-numDice):\n            #if left>f*d:\n                cache[(left,numDice)] = 0\n                return 0\n            if numDice == d:\n            # if d*f==\n                return 1 if left == 0 else 0\n            else:\n                for face in faces:\n                    numDice += 1\n                    if left-face>=0:\n                        re += dfs(left-face,numDice)\n                    numDice -= 1\n                \n                cache[(left,numDice)] = re\n                return re\n        return dfs(target,0)%(10**9 + 7)", "from functools import lru_cache\n\nMOD = 10 ** 9 + 7\n\nclass Solution:\n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        sol = [0] * (target + 1)\n        sol[0] = 1\n        for _ in range(1,d+1):\n            nxt = [0] * (target + 1)\n            for i in range(target + 1):\n                start, end = max(i-f, 0), i-1\n                nxt[i] = sum(sol[start:end+1]) % MOD\n            sol = nxt\n        return sol[target]", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d*f < target: \n            return 0        # Handle special case, it speed things up, but not necessary\n        elif d*f == target: \n            return 1     # Handle special case, it speed things up, but not necessary\n        mod = int(10**9 + 7)\n        dp = [[0] * (target+1) for _ in range(d+1)] \n        for j in range(1, min(f+1, target+1)): \n            dp[1][j] = 1\n        for i in range(2, d+1):\n            for j in range(1, target+1):\n                for k in range(1, f+1):\n                    if j - k >= 0: dp[i][j] += dp[i-1][j-k]\n                dp[i][j] %= mod        \n        return dp[-1][-1] \n                    \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        res = [[0 for _ in range(target + 1)] for _ in range(d + 1)]\n        modula = (10**9)+7\n        res[0][0] = 1\n        for dice in range(1, d + 1):\n            for i in range(dice, target + 1):\n                interestMinRange = max(0, i - f)\n                res[dice][i] = sum(res[dice - 1][interestMinRange:i]) % modula\n        return res[-1][-1]\n                \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n    \n        memo = {}\n        \n        def helper(dices, total):\n            # print(dices, total)\n            if total < 0:\n                return 0\n            if dices == 0 and total == 0:\n                return 1\n            if dices > 0 and total == 0:\n                return 0\n            if dices * f < total:\n                memo[(dices, total)] = 0\n                return 0\n\n            if (dices, total) in memo:\n                return memo[(dices, total)]\n            \n            ways = 0\n            for num in range(1, f + 1):\n                ways += helper(dices - 1, total - num)\n            \n            memo[(dices, total)] = ways\n            # print(ways)\n            return ways\n        \n        return helper(d, target) % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d, f, target):\n        if (target < d) or (target > d*f): return 0\n        dp = [[0 for _ in range(d*f+1)] for _ in range(d+1)]\n        for v in range(1, f+1):\n            dp[1][v] = 1\n        for dcnt in range(2, d+1):\n            for total in range(dcnt, target+1):\n                for v in range(1, f+1):\n                    dp[dcnt][total] += dp[dcnt-1][total-v]\n        return dp[d][target] % (10**9 + 7)\n    \nclass Solution:\n    def numRollsToTarget(self, d, f, target):\n        if (target < d) or (target > d*f): return 0\n        dp = [[0 for _ in range(d*f+1)] for _ in range(d+1)]\n        for v in range(1, f+1):\n            dp[1][v] = 1\n        for dcnt in range(2, d+1):\n            for total in range(dcnt, target+1):\n                for v in range(1, f+1):\n                    dp[dcnt][total] += dp[dcnt-1][total-v]\n        return dp[d][target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target < d or target > d * f:\n            return 0\n        mod_val = 10 ** 9 + 7\n        dp = [0] * (target + 1)\n        dp[0] = 1\n        for r in range(1, d + 1):\n            if r > 1:\n                dp[r - 2] = 0\n            for i in range(target, r - 1, -1):\n                dp[i] = sum(dp[max(0, i - f) : i]) % mod_val\n        return dp[target]\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n           if target<d or target>d*f:\n                return 0\n           if target==d*f:\n              return 1\n           mem={};mod=int(1e9+7)\n           def dice(k,target):\n                if target==0:\n                    return 0\n                if k==1:\n                    if target<=f:\n                       return 1\n                    else:\n                        return 0\n                if (k,target) in mem:\n                    return mem[(k,target)]\n                ans=0 \n                for i in range(1,f+1):\n                    if target>=i and target<=f*k:\n                        ans+=dice(k-1,target-i)%mod\n                ans%=mod\n                mem[(k,target)]=ans\n                return ans\n           return dice(d,target) ", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        module = 10 ** 9 + 7\n        \n        \n        \n        self.m = {}\n        \n        def dfs(d,f,target):\n            \n            if d == 0 and target == 0:\n                return 1\n            \n            if d == 0 and target != 0:\n                return 0\n            if d*f < target or d > target:\n                return 0\n            \n            if (d, target) in self.m:\n                return self.m[(d, target)]\n            \n            \n            res  = 0\n            for i in range(1, f+1):\n                res = (res + dfs(d - 1, f, target - i)) % module\n\n            self.m[(d,target)] = res\n            return res\n\n        return dfs(d,f,target)\n            \n            \n        \n       \n            \n            \n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        module = 10 ** 9 + 7\n        \n        \n        \n        self.m = {}\n        \n        def dfs(d,f,target):\n            \n            if d == 0 and target == 0:\n                return 1\n            \n            if d == 0 and target != 0:\n                return 0\n            if d*f < target or d > target:\n                return 0\n            \n            if (d, target) in self.m:\n                return self.m[(d, target)]\n            \n            \n            res  = 0\n            for i in range(1, f+1):\n                res = (res + dfs(d - 1, f, target - i)) % module\n\n            self.m[(d,target)] = res\n            return res\n\n        return dfs(d,f,target)\n            \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target > d*f or target < d:\n            return 0\n    \n        targets = {}\n        faces = [i for i in range(1,f+1)]\n        \n        def solve(target,numDice):\n            ways = 0\n            if (target,numDice) in targets:\n                return targets[(target,numDice)]\n            if target > f*(d-numDice):\n                targets[(target,numDice)]=0\n                return 0\n            if numDice==d:\n                return 1 if target==0 else 0\n            else:\n                for face in faces:\n                    if target-face>=0:\n                        ways += solve(target-face,numDice+1)\n                \n                targets[(target,numDice)]=ways\n                return ways\n        return solve(target,0)%(10**9+7)\n        \n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        def foo(dices, need):\n            if dices == 0: return int(need==0)\n            elif (dices, need) in m: return m[(dices, need)]\n            elif need > f*dices: m[(dices, need)] = 0; return 0\n            ret = 0\n            for i in range(1,f+1):\n                ret += foo(dices-1, need-i)\n            m[(dices, need)] = ret\n            return ret\n        m = {}\n        return foo(d, target)%(10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target > f*d:\n            return 0\n        \n        dp = [[0 for _ in range(target + 1)] for _ in range(d + 1)]\n        dp[0][0] = 1\n        \n        for i in range(d + 1):\n            for j in range(1, target + 1):\n                for k in range(1, f + 1):\n                    if k > j:\n                        continue\n                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k])%(10 ** 9 + 7)\n        \n        return dp[-1][-1]\n", "MOD = (10 ** 9) + 7\nfrom collections import defaultdict\n\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        \n        if target > f*d: return 0\n        if target == f*d: return 1\n        \n        def F(j,memo,left):\n            if (j,left) in memo.keys(): return memo[(j,left)]\n            \n            if left < 0: return 0\n            \n            if j == d-1:\n                memo[(j,left)] = int(left <= f and left >= 1)\n                return memo[(j,left)]\n            \n            ans = 0\n            for i in range(1,f+1):\n                ans += F(j+1,memo,left - i)\n                \n            memo[(j,left)] = ans\n            return memo[(j,left)]\n            \n            \n        F(0,memo,target)\n        \n        return memo[(0,target)] % MOD", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        if d*f < target:\n            return 0\n        elif d*f == target:\n            return 1\n        \n        dp = [[0]*(target+1) for _ in range(d+1)]\n        for i in range(1, min(f+1, target+1)):\n            dp[1][i] = 1\n        \n        print(dp)\n        \n        for i in range(1,d+1):\n            for j in range(1,target+1):\n                for k in range(1,f+1):\n                    if k <= j:\n                        dp[i][j] += dp[i-1][j-k]\n                    dp[i][j] %= (10**9+7) \n            \n        print(dp)\n        return dp[-1][-1] ", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d*f < target: return 0\n        if d*f == target: return 1\n        \n        def dfs(j,left,memo):\n            \n            if (j,left) in memo.keys():\n                return memo[(j,left)]\n            \n            if left < 0:\n                return 0\n            \n            if j == d-1:\n                return int(left > 0 and left <= f)\n            \n            ans = 0\n            for i in range(1,f+1):\n                ans += dfs(j+1,left-i,memo)\n            \n            memo[(j,left)] = ans\n            \n            return memo[(j,left)]\n        \n        return dfs(0,target,{}) % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        matrix = [[1 if 1 <= x <= f and y == 0 else 0 for x in range(target+1) ] for y in range(0, d)]\n        for row in range(1, d):\n            for col, val in enumerate(matrix[row]):\n                matrix[row][col] = sum(matrix[row-1][max(0, col-f):max(0, col)])\n        \n        return matrix[d-1][target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target < d or target > d * f:\n            return 0\n        dp = [0] * (target + 1)\n        dp[0] = 1\n        mod_val = 10 ** 9 + 7\n        for r in range(1, d + 1):\n            if r > 1:\n                dp[r - 2] = 0\n            for i in range(target, r - 1, -1):\n                dp[i] = sum(dp[max(0, i - f) : i]) % mod_val\n        return dp[target]", "# REMEMBER: WHERE TO PUT THE MEMOIZE SAVE AND LOOKUP LINES IN THE RECURSIVE FUNCTION.\n# 1. BEFORE any work is done + AFTER all the work is done and we're about to return the answer.\n\nclass Solution:\n    def __init__(self):\n        self.memo = {} # maps (d, target) to num ways.\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # obvious base case.\n        if d * f < target:\n            return 0\n        if d == 1:\n            return 1\n        \n        if (d, target) in self.memo:\n            return self.memo[(d, target)]\n        # we do it recursively\n        numWays = 0\n        #for i in range(f, 0, -1):\n        for i in range(1, f+1):\n            # we roll with i, then we\n            if target - i > 0:            \n                ways = self.memo.get((d-1, target - i), self.numRollsToTarget(d - 1, f, target - i))\n                numWays += ways\n        self.memo[(d, target)] = numWays\n        return numWays % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d*f < target:\n            return 0\n        if d*f == target:\n            return 1\n        dp = [[0]*(target+1) for i in range(d+1)]\n        for i in range(1, min(f+1, target+1)):\n            dp[1][i] = 1\n        for i in range(2,d+1):\n            for j in range(1,target+1):\n                for k in range(1,f+1):\n                    if j-k >= 0:\n                        dp[i][j] += dp[i-1][j-k]\n                    dp[i][j] %= 10**9+7\n        return dp[-1][-1]", "# REMEMBER: WHERE TO PUT THE MEMOIZE SAVE AND LOOKUP LINES IN THE RECURSIVE FUNCTION.\n# 1. BEFORE any work is done + AFTER all the work is done and we're about to return the answer.\n\nclass Solution:\n    def __init__(self):\n        self.memo = {} # maps (d, target) to num ways.\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # obvious base case.\n        if d * f < target:\n            return 0\n        if d == 1:\n            return 1\n        \n        if (d, target) in self.memo:\n            return self.memo[(d, target)]\n        # we do it recursively\n        numWays = 0\n        for i in range(f, 0, -1):\n        #for i in range(1, f+1):\n            # we roll with i, then we\n            if target - i > 0:            \n                ways = self.memo.get((d-1, target - i), self.numRollsToTarget(d - 1, f, target - i))\n                numWays += ways\n        self.memo[(d, target)] = numWays\n        return numWays % (10**9 + 7)", "class Solution:\n    \n    MODULO = 10**9 + 7\n    table = {}\n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        return self.recursive(d, f, target) % self.MODULO\n        \n    def recursive(self, d: int, f: int, target: int):\n        if target < d or target > d*f: \n            return 0\n        if d == 1 and target <= f:\n            return 1\n        sum_ = 0\n        for i in range(1, f+1):\n            idx = (d - 1, f, target - i)\n            if idx not in self.table:\n                self.table[idx] = self.recursive(*idx)\n            sum_ += self.table[idx] % self.MODULO\n        return sum_", "class Solution:\n    def __init__(self):\n        self.memo = {} # maps (d, target) to num ways.\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # obvious base case.\n        if d * f < target:\n            return 0\n        if d == 1:\n            return 1\n        \n        if (d, target) in self.memo:\n            return self.memo[(d, target)]\n        # we do it recursively\n        numWays = 0\n        for i in range(f, 0, -1):\n            # we roll with i, then we\n            if target - i > 0:            \n                ways = self.memo.get((d-1, target - i), self.numRollsToTarget(d - 1, f, target - i))\n                numWays += ways\n        self.memo[(d, target)] = numWays\n        return numWays % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo = {}\n        def solve(dice, target):\n            if target > dice*f:\n                memo[dice, target] = 0\n                return 0\n            if dice == 0:\n                return target == 0\n            if target == 0:\n                return 0\n            if (dice, target) in memo:\n                return memo[dice, target]\n            ways = 0\n            for num in range(1, f+1):\n                ways += solve(dice-1, target-num)\n            memo[dice, target] = ways\n            return ways\n            \n            \n        return solve(d, target)%(10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target > d*f:\n            return 0\n        dp = [[0 for _ in range(d*f+1)] for _ in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1, d+1):\n            for j in range(i, i*f+1):\n                for t in range(1, f+1):\n                    if (j-t) >= i-1 and (j-t) <= (i-1)*f:\n                        dp[i][j] += dp[i-1][j-t]\n        return dp[d][target] % (10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        memo= {}\n        def rolls(dice, t):\n            if t > f * dice:\n                memo[(dice, t)] = 0\n                return 0\n            if dice == 0:\n                return t == 0\n            if target < 0:\n                return 0\n            if (dice, t) in memo:\n                return memo[(dice, t)]\n            solu = 0\n            for num in range(1, f + 1):\n                solu += rolls(dice - 1, t - num)\n            memo[(dice, t)] = solu\n            return solu\n        return rolls(d, target) % (10**9 + 7)\n                \n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        @lru_cache(None)\n        def dfs(dice_left, curr_sum):\n            if curr_sum > target:\n                return 0\n            if dice_left == 0:\n                return 1 if curr_sum == target else 0\n            count = 0\n            for i in range(1, f + 1):\n                count += dfs(dice_left - 1, curr_sum + i)\n            return count % 1000000007\n        return dfs(d, 0)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        MOD = 10 ** 9 + 7\n\n        @lru_cache(None)\n        def dp(dice, target):\n            # number of ways to form target with `dice` remaining\n            if target == 0:\n                return int(dice == 0)\n            elif target < 0 or dice <= 0:\n                return 0\n            else: # target >= 0 and dice >= 0\n                res = 0\n                for x in range(1, f + 1):\n                    res += dp(dice - 1, target - x)\n                return res % MOD\n\n        return dp(d, target)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target < d or target > d * f:\n            return 0\n        dp = [0] * (target + 1)\n        dp[0] = 1\n        mod_val = 10 ** 9 + 7\n        for r in range(1, d + 1):\n            if r > 1:\n                dp[r - 2] = 0\n            for i in range(target, r-1, -1):\n                dp[i] = sum(dp[max(0, i - f) : i]) % mod_val\n        return dp[target]", "import functools\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        @functools.lru_cache(None)\n        def helper(idx, curr):\n            if curr > target: return 0\n            if idx == d:\n                return int(curr == target)\n            res = 0\n            for num in range(1, f + 1):\n                res += helper(idx + 1, curr + num)\n            return res % (10 ** 9 + 7)\n        return helper(0, 0)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        MOD = 10 ** 9 + 7\n\n        @lru_cache(None)\n        def dp(dice, target):\n            if dice == 0:\n                return int(target == 0)\n            elif target <= 0: # and dice > 0\n                return 0\n            else: # target > 0 and dice > 0\n                res = 0\n                for x in range(1, f + 1):\n                    res += dp(dice - 1, target - x)\n                return res % MOD\n\n        return dp(d, target)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n            @lru_cache(maxsize=None)\n            def nrolls(d, t):\n                if d == 0:  \n                    if t == 0:\n                        return 1    \n                    else:\n                        return 0\n                if d > t or t < 0: \n                    return 0\n                res = 0\n                for i in range(1, f+1):\n                    res += nrolls(d-1, t-i)\n                return res % ((10 ** 9) + 7)\n            return nrolls(d, target) ", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        if target > d*f:\n            return 0\n        dicti = collections.defaultdict(int)\n        def dice_target(rem_dice, summ):\n            if rem_dice == 0:\n                return 1 if summ == target else 0\n            if summ > target:\n                return 0\n            if (rem_dice, summ) in dicti:\n                return dicti[rem_dice, summ]\n\n            for i in range(1, f+1):\n                dicti[rem_dice, summ] += dice_target(rem_dice-1, summ+i)\n            return dicti[rem_dice, summ]\n        \n        \n        return dice_target(d, 0) % (10**9 + 7)\n\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d * f < target:\n            return 0\n        elif d * f == target:\n            return 1\n        \n        dp = [[0] * (target+1) for _ in range(d)] # dp[i][j]: solution for target j with i + 1 dices\n        BASE = 10**9 + 7\n        for j in range(1, min(f, target)+1):\n            dp[0][j] = 1\n        for i in range(1, d):\n            for j in range(target+1):\n                for k in range(1, f+1):\n                    if k >= j: break\n                    dp[i][j] += dp[i-1][j-k] % BASE\n        \n        return dp[d-1][target] % BASE", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        if target > d*f:\n            return 0\n        \n        dicti = collections.defaultdict(int)\n        def dice_target(rem_dice, summ):\n            if rem_dice == 0:\n                return 1 if summ == target else 0\n            if summ > target:\n                return 0\n            if (rem_dice, summ) in dicti:\n                return dicti[rem_dice, summ]\n\n            for i in range(1, f+1):\n                dicti[rem_dice, summ] += dice_target(rem_dice-1, summ+i)\n            return dicti[rem_dice, summ]\n        \n        \n        return dice_target(d, 0) % (10**9 + 7)\n\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [0]*(target+1)\n        \n        for i in range(1,f+1):\n            if i<=target:\n                dp[i] = 1\n        temp = dp[:]\n        for i in range(1,d):\n            dp = [0]*(target+1)\n\n            for t in range(1, target+1):              \n                if temp[t]>0:\n                    for k in range(1,f+1):\n                        if t+k <= target:\n                            dp[t+k]+= temp[t]%(10**9 + 7) \n           \n            for t in range(1,target+1):\n                dp[t]=dp[t]  %(10**9 + 7) \n            temp = dp[:]\n    #    print(929256393%(10**9 + 7) )\n        return dp[target]%(10**9 + 7) \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d * f < target or d > target:\n            return 0\n    \n        if d == 1 and f >= target:\n            return 1\n        \n        rows = d+1\n        cols = target+1\n        dp = [[0 for _ in range(cols)] for _ in range(rows)]\n            \n        for i in range(1,min(f+1, cols)):\n            dp[1][i] = 1\n\n            \n        for i in range(2, rows):\n            for j in range(i, cols):\n                \n                start = max(1, j - f)\n                dp[i][j] = sum(dp[i-1][start:j]) % 1000000007\n                \n                \n        return dp[d][target]\n                \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # 2. Bottom-up Dynamic Programming\n        dp = [[0 for _ in range(target + 1)] for _ in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1, d + 1):\n            for j in range(i*1, min(target+1, i*f + 1)):\n                for r in range(1, f+1):\n                    if j - r >= 0:\n                        dp[i][j] += dp[i-1][j-r]\n        return dp[-1][-1] % (10**9 + 7)\n                \n                \n            \n#             1 dice -> 1 , f\n#             2 dices -> 2, 2f\n\n   \n        \n        # 1. Recursion: O(F^D) Time, O(F^D) Space\n        self.res = 0\n        def dfs(dice, sum):\n            for i in range(1, f+1):\n                if dice == d:\n                    if sum + i == target:\n                        self.res += 1\n                elif sum + i < target:\n                    dfs(dice + 1, sum + i)\n        dfs(1, 0)\n        return self.res\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        @lru_cache(None)\n        def dfs(rsum,d):\n            \n            if d==0 and rsum==0:\n                return 1\n            \n            elif rsum==0 or d==0:\n                return 0\n            \n            res=0\n            for i in range(1,f+1):\n                if rsum-i>=0:\n                    res+=dfs(rsum-i,d-1)\n                    \n            return res\n        \n        \n        return dfs(target,d)%(10**9+7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = [[0 for j in range(target + 1)] for i in range(d + 1)]\n        for dd in range(1, d + 1):\n            for tt in range(dd, min(dd * f, target) + 1):\n                if dd == 1:\n                    dp[dd][tt] = 1\n                else:\n                    for i in range(1, f + 1):\n                        if tt - i >= 1:\n                            dp[dd][tt] += dp[dd - 1][tt - i]\n        return dp[dd][target] % (10**9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # 2. Bottom-up Dynamic Programming\n        #   DP Array where target is the column and numDices is the row\n        \n        #   Range of values:\n        #   1 dice -> (1 , f)\n        #   2 dices -> (2, 2f)\n        #   d dices -> (d, fd)\n        dp = [[0 for _ in range(target + 1)] for _ in range(d+1)]\n        dp[0][0] = 1\n        for i in range(1, d + 1):\n            for j in range(i*1, min(target+1, i*f + 1)):\n                for r in range(1, f+1):\n                    if j - r >= 0:\n                        dp[i][j] += dp[i-1][j-r]\n        return dp[-1][-1] % (10**9 + 7)\n\n    \n        # 1. Recursion: O(F^D) Time, O(F^D) Space\n        self.res = 0\n        def dfs(dice, sum):\n            for i in range(1, f+1):\n                if dice == d:\n                    if sum + i == target:\n                        self.res += 1\n                elif sum + i < target:\n                    dfs(dice + 1, sum + i)\n        dfs(1, 0)\n        return self.res\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if not d or not f or target == 0:\n            return 0\n            \n        def dfs(d, f, hash_map, target):\n            \n            \n            if target == 0 and d == 0:\n                return 1\n            if target<=0 or target>d*f or target<d:\n                return 0\n            \n            # logic\n            if (d,target) in hash_map:\n                return hash_map[(d,target)]\n            \n            cnt = 0\n            for i in range(1, f+1):\n                if target-i<0:\n                    break\n                cnt += dfs(d-1, f,hash_map, target-i)\n                cnt %= 1000000007\n\n            hash_map[(d,target)] = cnt\n            return hash_map[(d,target)]\n        \n        return dfs(d,f,{},target)\n    \n\n  \n    \n\n        \n", "class Solution:\n    # Recursive memoized solution\n#     def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n#         memo = {}\n#         def num_rolls_util(level, target):\n#             if level * f < target or target < level:\n#                 return 0\n#             if level == 0:\n#                 return 1\n            \n#             res = 0\n#             for i in range(max(0, target - f), target):\n#                 if (level-1, i) in memo:\n#                     res += memo[(level-1, i)]\n#                 else:\n#                     tmp = num_rolls_util(level - 1, i)\n#                     memo[(level-1, i)] = tmp\n#                     res += tmp\n\n#             return res % (10 ** 9 + 7)\n        \n#         return num_rolls_util(d, target)\n    \n    \n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mod = 10 ** 9 + 7\n        dp = [[0] * (target + 1) for _ in range(d+1)]\n        dp[0][0] = 1\n        \n        for i in range(1, d+1):\n            for j in range(1, min(target, i * f) + 1):\n                for k in range(1, min(j, f) + 1):\n                    dp[i][j] += dp[i-1][j-k] % mod\n        \n        return dp[d][target] % mod        ", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d <= target <= d*f:\n            mod = 10**9 + 7\n            def rec(d, f, t):\n                \n                if d == 1:\n                    return 1 if 0 < t <= f else 0\n                elif (d, t) in memo:\n                    return memo[(d, t)]\n                else:\n                    temp = sum([rec(d-1, f, t-x) for x in range(1, f+1)])\n                    memo[(d, t)] = temp\n                    return temp\n            memo = {}\n            return rec(d, f, target) % mod\n        return 0", "'''\n1155. Number of Dice Rolls With Target Sum.  Medium\n\nYou have d dice, and each die has f faces numbered 1, 2, ..., f.\n\nReturn the number of possible ways (out of fd total ways) modulo 10^9 + 7 \nto roll the dice so the sum of the face up numbers equals target.\n\nExample 1:\nInput: d = 1, f = 6, target = 3\nOutput: 1\nExplanation: \nYou throw one die with 6 faces.  There is only one way to get a sum of 3.\n\nExample 2:\nInput: d = 2, f = 6, target = 7\nOutput: 6\nExplanation: \nYou throw two dice, each with 6 faces.  There are 6 ways to get a sum of 7:\n1+6, 2+5, 3+4, 4+3, 5+2, 6+1.\n\nExample 3:\nInput: d = 2, f = 5, target = 10\nOutput: 1\nExplanation: \nYou throw two dice, each with 5 faces.  There is only one way to get a sum of 10: 5+5.\n\nExample 4:\nInput: d = 1, f = 2, target = 3\nOutput: 0\nExplanation: \nYou throw one die with 2 faces.  There is no way to get a sum of 3.\n\nExample 5:\nInput: d = 30, f = 30, target = 500\nOutput: 222616187\nExplanation: \nThe answer must be returned modulo 10^9 + 7.\n\nConstraints:\n1 <= d, f <= 30\n1 <= target <= 1000\n\nAccepted\n49,213\nSubmissions\n101,895\n'''\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if d <= target <= d*f:\n            mod = 10**9 + 7\n            def rec(d, f, t):\n                if d == 1:\n                    return 1 if 0 < t <= f else 0\n                elif (d, t) in memo:\n                    return memo[(d, t)]\n                else:\n                    temp = sum([rec(d-1, f, t-x) for x in range(1, f+1)])\n                    memo[(d, t)] = temp\n                    return temp\n            memo = {}\n            return rec(d, f, target) % mod\n        return 0", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        dp = {}\n        \n        for i in range(1, f+1):\n            dp[i] = 1\n            \n        for i in range(d-1):\n            temp = {}\n            for val in dp:\n                for dice in range(1, f+1):\n                    if val + dice <= target:\n                        temp[val+dice] = temp.get(val+dice, 0) + dp[val]\n            dp = temp\n                \n        if not target in dp:\n            return 0\n        return dp[target]  % (10**9 + 7)\n                    \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        # 2. Bottom-up Dynamic Programming\n        #   DP Array where target is the column and numDices is the row\n        \n        #   Range of values:\n        #   1 dice -> (1 , f)\n        #   2 dices -> (2, 2f)\n        #   d dices -> (d, fd)\n        dp = [[0 for _ in range(target + 1)] for _ in range(d+1)]\n        dp[0][0] = 1\n        for n in range(1, d + 1):\n            for i in range(1*n, min(target+1, f*n + 1)):\n                for j in range(1, f+1):\n                    if i - j >= 0:\n                        dp[n][i] += dp[n-1][i - j]\n        return dp[-1][-1] % (10**9+7)\n\n    \n        # 1. Recursion: O(F^D) Time, O(F^D) Space\n        self.res = 0\n        def dfs(dice, sum):\n            for i in range(1, f+1):\n                if dice == d:\n                    if sum + i == target:\n                        self.res += 1\n                elif sum + i < target:\n                    dfs(dice + 1, sum + i)\n        dfs(1, 0)\n        return self.res\n", "class Solution:\n    def __init__(self):\n        self.mem = {}\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        if target < d or target > d*f:\n            return 0\n        if d == 0 or target == 0:\n            return 0\n        if d==1 and target <= f:\n            return 1\n        key = (d,f,target)\n        if key in self.mem:\n            return self.mem[key]\n        Sum = 0\n        for i in range(1,f+1):\n            Sum += self.numRollsToTarget(d-1, f, target-i)\n            Sum %= (10**9+7)\n        self.mem[key] = Sum\n        return (self.mem[key])\n        \n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        @lru_cache(None)\n        def solve(s,t):\n            if s <= 0:\n                if t == 0:return 1\n                return 0\n            ans = 0\n            for i in range(1,f+1):\n                if t >= i:\n                    ans += solve(s - 1,t - i)\n            return ans\n        \n        return solve(d,target) % (10**9+7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        \n        @lru_cache(None)\n        def dfs(left, k):\n            if left == k:\n                return 1\n            \n            if left > k:\n                return 0\n            \n            if k == 0:\n                if left == 0:\n                    return 1\n                else:\n                    return 0\n            \n            if left < 0 :\n                return 0\n            \n            \n            s = 0\n            for i in range(1, f+1):\n                if k - i < 0:\n                    break\n                s += dfs(left-1, k - i)\n            \n            return s % (10 ** 9 + 7)\n        \n        return dfs(d, target) % (10 ** 9 + 7)", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        current_sums = {}\n        current_sums[0] = 1\n        new_sums = {}\n        out = 0\n        \n        for die in range(1, d+1):\n            for face in range(1, f+1):\n                for summ in list(current_sums.keys()):\n                    curr = summ+face\n                    if curr == target and die == d:\n                        out += current_sums[summ]\n                    elif curr < target:\n                        if curr in list(new_sums.keys()):\n                            new_sums[curr] += current_sums[summ]\n                        else:\n                            new_sums[curr] = current_sums[summ] \n                    \n            current_sums = new_sums\n            # print(current_sums)\n            new_sums = {}\n        \n        return out % (10**9 + 7)\n\n        # need to go through from target backwards suubtracting face everytime and adding to possibilities\n    \n    \n#         def helper(h, d, target):\n#             # if target is too small or if it is out of range\n#             if target <= 0 or target > (d * f):\n#                 return 0\n#             if d == 1:\n#                 print(d,f,target)\n#                 return 1        # no need to check if target is within reach; already done before\n#             if (d, target) in h:\n#                 return h[(d, target)]        # directly access from hash table\n#             res = 0\n#             for i in range(1, f + 1):\n#                 res += helper(h, d - 1, target - i)       # check all possible combinations\n#             h[(d, target)] = res\n#             return h[(d, target)]\n        \n#         h = {}\n#         return helper(h, d, target) % (10 ** 9 + 7)\n", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        @lru_cache(maxsize=None)\n        def func(d, target):\n            if d == 0:\n                return 1 if target==0 else 0\n            if d>target or target<0:\n                return 0\n            return sum([func(d-1, target-i)%(1e9+7) for i in range(1, f+1)])%(1e9+7)\n        \n        if d<1 or f<1 or target<1:\n            return 0\n        return int(func(d, target))", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        @lru_cache(None)\n        def solve(s,t):\n            if s <= 0 or t < 0:\n                if t == 0:return 1\n                return 0\n            ans = 0\n            for i in range(1,f+1):\n                ans += solve(s - 1,t - i)\n            return ans\n        return solve(d,target) % (10**9+7)", "from functools import lru_cache\nMOD=10**9+7\nclass Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        @lru_cache(None)\n        def dp(i,k):\n            if i == d:\n                return k==0\n            return sum(dp(i+1,k-face) for face in range(1,f+1))\n        return dp(0, target) % MOD", "class Solution:\n    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        \n        if d == 1:\n            return 1 if f >=target else 0\n        \n        dp = [[0 for _ in range(target+1)] for _ in range(d+1)]\n        dp[0][0] = 1\n        \n        for i in range(1, d+1):\n            for j in range(i, min(i*f, target)+1):\n                # to ensure j-k >=0 means, k <=j, \u81f3\u591a\u4e3aj,min(j, f)\n                for k in range(1, min(j, f)+1):\n                    dp[i][j] += dp[i-1][j-k]\n        \n        return dp[d][target] % (pow(10, 9)+7)\n    \n    def __numRollsToTarget(self, d: int, f: int, target: int) -> int:\n        mem = {}\n        return self.dp(d, f, target, mem) % (pow(10, 9) + 7)\n    \n    def dp(self, d, f, target, mem):\n        if d==0:\n            return 1 if target == 0 else 0\n        \n        if d*f < target:\n            return 0\n        \n        if (d, target) in mem:\n            return mem[(d, target)]\n        \n        res = 0\n        for i in range(1, f+1):\n            if target -i < 0:\n                break\n            res += self.dp(d-1, f, target-i, mem)\n        \n        mem[(d, target)] = res\n        return res"]