Python modulo returning wrong answer

Question

I was attempting this question on leetcode using python3. My solution for this problem is as follows:

class Solution:
    def __init__(self):
        self.memo = {}
        
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        
        if target < d or target > d*f: return 0
        if d == 1:
            if target<=f: return 1
            else: return 0
        
        
        key = d+f+target

        if key not in self.memo:
            total = 0
            for i in range(1,f+1):
                if key not in self.memo:
                    total += self.numRollsToTarget(d-1,f,target-i)
            self.memo[key] = total%((10**9) + 7)
        return self.memo[key]

My solution works for small inputs like: Input: n = 1, k = 6, target = 3 Output: 1 Explanation: You throw one die with 6 faces. There is only one way to get a sum of 3. However inputs such as Input: n = 30, k = 30, target = 500 Output: 222616187 Explanation: The answer must be returned modulo 109 + 7. do not pass the test cases, even when I have made sure that I return the modulo answer. For example for the second test case, the correct output is 222616187. However, my code returns 146996393. Can anyone point out where I am going wrong?

Answer 1

d+f+target is not a unique key for the tuple (d, f, target), which makes the memoization yield incorrect results. Using the tuple (d, f, target) itself is a simple fix.

Also it is unclear why there is a second if key not in self.memo: inside the loop. It shouldn't be possible for that condition to be changed by the computation of the sub-problems, and if it was possible then it would be the wrong way to do it because the wrong total is added up and written over the memo entry that apparently exists.