class Solution(object):
    def numRollsToTarget(self, d, f, target):
        """
        :type d: int
        :type f: int
        :type target: int
        :rtype: int
        """
        record = dict()
        def backtrack(dice, face, t):
            if (dice, face, t) in record: #Ѿ֪ǰĽ
                return record[(dice, face, t)] #ֱӶȡ
            
            if dice == 0: #ûӵʱжһǲǸպҵtarget
                return 1 if t == 0 else 0
            
            if t < 0 or dice <= 0: #Чʱûн⣬Է0
                return 0
            tmp = 0 #tmpڼ¼ǰжٸ
            for i in range(1, face + 1): #е
                tmp += backtrack(dice - 1, face, t - i) 
                
            record[(dice, face, t)] = tmp #ѽԺ
            return tmp
        
        backtrack(d, f, target)
        return max(record.values()) % (10 ** 9 + 7) #ĽĸĽ
                
            