class Solution:

    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        mem = {}
        return self.numRollsToTarg(d, f, mem, target)

    def numRollsToTarg(self, d, f, mem, targ):
        state = str(d) + str(f) + str(targ)
        if state in mem:
            return mem[state]
        if not d:
            return 1 if targ == 0 else 0
        ways = 0
        for face in range(1, f+1):
            ways += self.numRollsToTarg(d-1, f, mem, targ - face)
        mem[state] = ways % (10**9+7)
        return ways % (10**9+7)