<p>A die simulator generates a random number from <code>1</code> to <code>6</code> for each roll. You introduced a constraint to the generator such that it cannot roll the number <code>i</code> more than <code>rollMax[i]</code> (<strong>1-indexed</strong>) consecutive times.</p>

<p>Given an array of integers <code>rollMax</code> and an integer <code>n</code>, return <em>the number of distinct sequences that can be obtained with exact </em><code>n</code><em> rolls</em>. Since the answer may be too large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>Two sequences are considered different if at least one element differs from each other.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2, rollMax = [1,1,2,2,2,3]
<strong>Output:</strong> 34
<strong>Explanation:</strong> There will be 2 rolls of die, if there are no constraints on the die, there are 6 * 6 = 36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 = 34.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2, rollMax = [1,1,1,1,1,1]
<strong>Output:</strong> 30
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 3, rollMax = [1,1,1,2,2,3]
<strong>Output:</strong> 181
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 5000</code></li>
	<li><code>rollMax.length == 6</code></li>
	<li><code>1 &lt;= rollMax[i] &lt;= 15</code></li>
</ul>

class Solution:
    # class Solution:
    
    # def dieSimulator(self, n: int, rollMax: List[int]) -> int:
    #     faces = len(rollMax)
    #     # [n + 1][faces + 1] dimensional dp array
    #     dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
    #     # initialization
    #     # roll 0 times, the total combination is 1
    #     dp[0][faces] = 1
    #     # roll 1 times, the combinations that end at face j is 1
    #     for j in range(faces):
    #         dp[1][j] = 1
    #     # roll 1 times, the total combination is faces = 6
    #     dp[1][faces] = faces
        
    #     # then roll dices from 2 times, until n times
    #     for i in range(2, n + 1):
    #         # iterate through each column (face)
    #         for j in range(faces):
    #             # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state
    #             for k in range(1, rollMax[j] + 1):
    #                 if i - k < 0:
    #                     break
    #                 dp[i][j] += dp[i - k][faces] - dp[i - k][j]
    #         # update total sum of this row
    #         dp[i][faces] = sum(dp[i])
        
    #     return dp[n][faces] % 1000000007
    
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        '''
        3 111223
        2 000112
        1 000001
        
        6 * 6 * 6 -> -5 - 5
        '''
        arr = {}
        for i in range(len(rollMax)):
            arr[i] = rollMax[i]
        
        @cache
        def allowed(roll, lastpick, streak):
            if roll == lastpick:
                return streak < arr[roll]
            return True
            
        @cache
        def recurse(rolls, last, streak):
            if rolls == n:
                # print(path)
                return 1
            out = 0
            
            for pick in range(6):
                if allowed(pick, last, streak):
                    new_streak = streak+1
                    if pick == last:
                        out += recurse(rolls+1, pick, new_streak)
                    else:
                        out += recurse(rolls+1, pick, 1) 
                        out %= ((10**9) + 7)
                    
            return out % ((10**9) + 7)
        
        return recurse(0, -1, 0) % ((10**9) + 7)
                    

        '''
        111
        211
        311

        '''
160256