A die simulator generates a random number from 1 to 6 for each roll. You introduced a constraint to the generator such that it cannot roll the number i more than rollMax[i] (1-indexed) consecutive times. 
Given an array of integers rollMax and an integer n, return the number of distinct sequences that can be obtained with exact n rolls.
Two sequences are considered different if at least one element differs from each other. Since the answer may be too large, return it modulo 10^9 + 7.
 
Example 1:
Input: n = 2, rollMax = [1,1,2,2,2,3]
Output: 34
Explanation: 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.

Example 2:
Input: n = 2, rollMax = [1,1,1,1,1,1]
Output: 30

Example 3:
Input: n = 3, rollMax = [1,1,1,2,2,3]
Output: 181

 
Constraints:

1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15

Difficulty: interview

Starter code:

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        

Solutions:
["class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        a,b,m=[deque([0]*x) for x in rollMax],[1]*6,1000000007\n        for x in a: x[-1]=1\n        for _ in range(n-1):\n            s=sum(b)%m\n            for i,x in enumerate(a):\n                x.append((s-b[i])%m)\n                b[i]=(b[i]+x[-1]-x.popleft())%m\n        return sum(b)%m", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MODULO = 10**9 + 7\n        \n        n_num = len(rollMax)\n        \n        dp = [[0] * (n_num+1) for _ in range(n+1)]\n        dp[0][-1] = 1\n        \n        dp[1] = [1 for _ in range(n_num+1)]\n        dp[1][-1] = n_num\n        \n        for i in range(2, n+1):\n            dp[i] = [(dp[i-1][-1])] * (n_num+1)\n            for j in range(n_num):\n                k = i - rollMax[j]\n                if k > 0:\n                    dp[i][j] -= (dp[k-1][-1] - dp[k-1][j])\n                dp[i][j] = dp[i][j] % MODULO\n            dp[i][-1] = sum(dp[i][:-1]) % MODULO\n        \n        return dp[-1][-1]", "\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n\n        dp = [[0 for _ in range(7)] for i in range(n+1)]\n        kMod = 1e9 + 7\n\n        for i in range(1, 7):\n            dp[1][i] = 1\n\n        # steps\n        for i in range(2, n+1):\n\n            # current value\n            for j in range(1, 7):\n\n                k = i-rollMax[j-1]\n\n                # all the posibilities included invalid ones\n                dp[i][j] = sum(dp[i-1])\n\n                # take off invalid posibilities\n                invalid = max(0, k) if k <= 1 else (sum(dp[k-1])-dp[k-1][j])\n                dp[i][j] = ((dp[i][j]-invalid) % kMod+kMod) % kMod\n\n        return int(sum(dp[-1]) % (kMod))\n\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        dp = [[0 for _ in range(len(rollMax))] for _ in range(n + 1)]\n        sums_dict = {}\n        sums_dict[0] = 1\n        for j in range(len(rollMax)):\n            dp[1][j] = 1\n        \n        for i in range(2, n + 1):\n            sums_dict[i - 1] = sum(dp[i - 1])\n            for j in range(len(rollMax)):\n                steps = rollMax[j] # number of steps we can go upwards\n                k = 1\n                ans = 0\n                while k <= min(steps, i):\n                    row_sum = sums_dict[i - k]\n                    ans += row_sum - dp[i - k][j]\n                    k += 1\n                dp[i][j] = ans\n        \n        return sum(dp[n]) % (10**9 + 7)\n                \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod=10**9+7\n        dp=[[1]*6 for i in range(n)]\n        for i in range(1,n):\n            for j in range(6):\n                dp[i][j]=sum([dp[i-1][k] for k in range(6)])\n                if i==rollMax[j]:\n                    dp[i][j]-=1\n                if i>rollMax[j]:\n                    dp[i][j]-=sum([dp[i-rollMax[j]-1][k] for k in range(6) if k!=j])\n        return sum(dp[-1])%mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = pow(10, 9) + 7\n        dp = [[1] + [0 for _ in range(14)] for _ in range(6)]\n        \n        for _ in range(n - 1):\n            dp1 = [[0 for _ in range(15)] for _ in range(6)]\n            sums = [sum(s) for s in dp]\n            for num in range(6):\n                dp1[num][0] = sum(sums[0:num]) + sum(sums[num + 1:])\n                for x in range(1, 15):\n                    if x > rollMax[num] - 1: break\n                    dp1[num][x] = dp[num][x - 1]\n            \n            dp = dp1\n            \n        return sum([sum(l) for l in dp]) % mod", "from collections import defaultdict\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0]*7 for _ in range(n+1)]\n        prev = defaultdict(int)\n        \n        for i in range(1,7):\n            dp[1][i] = 1\n            prev[(i,1)] = 1\n        \n        for i in range(2, n+1):\n            new = defaultdict(int)\n            for j in range(1, 7):\n                new[(j, 1)] = dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4] + dp[i-1][5] + dp[i-1][6] - dp[i-1][j]\n                dp[i][j] += new[(j, 1)]\n                \n                max_len = min(15, rollMax[j-1])\n                for k in range(1, max_len):\n                    new[(j, k+1)] = prev[(j, k)]\n                    dp[i][j] += new[(j, k+1)]\n            prev = new\n        \n        \n        count = 0\n        for i in range(1,7):\n            count += dp[n][i]\n        return count%1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        # [n + 1][faces + 1] dimensional dp array\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        # initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n            # iterate through each column (face)\n            for j in range(faces):\n                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n            # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n\n        results = [[0 for _ in range(7)] for _ in range(n+1)]\n        results[0][6] = 1\n\n        for i in range(1, n+1):\n            for j in range(6):\n                suma = 0\n                for roll_max in range(min(rollMax[j], i)):\n                    suma += results[i-1-roll_max][6] - results[i-1-roll_max][j]\n                results[i][j] = suma\n            results[i][6] = sum(results[i])\n\n        return results[n][6] % (10**9 + 7)", "class Solution:\n#     https://leetcode.com/problems/dice-roll-simulation/discuss/404840/Short-Python-DP-with-detailed-image-explanation\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        record = [[0] * (faces+1) for _ in range(n+1)]\n        record[0][faces] = 1\n        for i in range(faces):\n            record[1][i] = 1\n        record[1][faces] = 6\n        for i in range(2,n+1):\n            for j in range(faces):\n                for k in range(1,rollMax[j]+1):\n                    if i - k < 0:\n                        break\n                    record[i][j] += record[i-k][faces] - record[i-k][j]\n            record[i][faces] = sum(record[i])\n        return record[-1][faces]%(10**9+7)  \n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp= [[0 for _ in range(7)] for _ in range(n+1)]\n        dp[0][6]=1\n        for r in range(1,n+1):\n            for f in range(6):\n                k = 1\n                while(k<=rollMax[f] and r-k>=0):\n                    dp[r][f] += dp[r-k][6]-dp[r-k][f] \n                    k +=1\n                \n            dp[r][6]=sum(dp[r][:6])\n        return (dp[-1][-1])%(10**9+7)", "\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n\n        # dp[at nth roll][count of current number (1~6)]\n        dp = [[[0 for _ in range(max(rollMax) + 1)]\n               for _ in range(7)] for _ in range(n + 1)]\n        kMod = 1e9 + 7\n        for i in range(1, 7):\n            dp[1][i][1] = 1\n\n        for i in range(2, n + 1):\n            for j in range(1, 7):\n                for l in range(1, 7):\n                    if l != j:\n                        dp[i][j][1] += sum(dp[i - 1][l]) % kMod\n                    else:\n                        for k in range(1, rollMax[j - 1] + 1):\n                            dp[i][j][k] += dp[i - 1][j][k - 1] % kMod\n\n        temp = sum([(sum(i) % kMod) for i in dp[-1]])\n\n        return int(temp % kMod)\n\n    def dieSimulator_temp(self, n: int, rollMax: List[int]) -> int:\n\n        dp = [[0 for _ in range(7)] for i in range(n+1)]\n        kMod = 1e9 + 7\n\n        for i in range(1, 7):\n            dp[1][i] = 1\n\n        # steps\n        for i in range(2, n+1):\n\n            # current value\n            for j in range(1, 7):\n\n                k = i-rollMax[j-1]\n\n                # all the posibilities included invalid ones\n                dp[i][j] = sum(dp[i-1])\n\n                # take off invalid posibilities\n                invalid = max(0, k) if k <= 1 else (sum(dp[k-1])-dp[k-1][j])\n                dp[i][j] = ((dp[i][j]-invalid) % kMod+kMod) % kMod\n\n        return int(sum(dp[-1]) % (kMod))\n\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n    \n    # initialization\n    # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n    # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n    # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n    \n    # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n        # iterate through each column (face)\n            for j in range(faces):\n                dp[i][j] = dp[i - 1][-1]\n                if i-1-rollMax[j] >= 0:\n                    dp[i][j] -= (dp[i-1-rollMax[j]][-1] - dp[i-1-rollMax[j]][j])\n        # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n    \n        return dp[n][faces]%1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        table = [[0 for _ in range(len(rollMax) + 1)] for _ in range(n + 1)]\n        table[0][len(rollMax)] = 1\n        \n        for j in range(len(rollMax)):\n            table[1][j] = 1\n            \n        table[1][len(rollMax)] = 6\n        \n        for i in range(2, n + 1):\n            for j in range(len(rollMax)):\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    table[i][j] += table[i - k][len(rollMax)] - table[i - k][j] \n            table[i][len(rollMax)] = sum(table[i])  \n        return table[-1][-1] % (10**9 + 7)\n", "class Solution:\n#     https://leetcode.com/problems/dice-roll-simulation/discuss/404840/Short-Python-DP-with-detailed-image-explanation\n    # Use a 2D dimensional board to record the possible number of times of one face at one throw\n    # The current times = previous K times (i-k<0) (each time, the total number of all faces - this number)\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        record = [[0] * (faces+1) for _ in range(n+1)]\n        record[0][faces] = 1\n        for i in range(faces):\n            record[1][i] = 1\n        record[1][faces] = 6\n        for i in range(2,n+1):\n            for j in range(faces):\n                for k in range(1,rollMax[j]+1):\n                    if i - k < 0:\n                        break\n                    record[i][j] += record[i-k][faces] - record[i-k][j]\n            record[i][faces] = sum(record[i])\n        return record[-1][faces]%(10**9+7)  \n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        # [n + 1][faces + 1] dimensional dp array\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        # initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n            # iterate through each column (face)\n            for j in range(6):\n                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n            # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007\n", "\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n\n        # dp[at nth roll][count of current number (1~6)]\n        dp = [[[0 for _ in range(max(rollMax) + 1)]\n               for _ in range(7)] for _ in range(n + 1)]\n        kMod = 1e9 + 7\n        for i in range(1, 7):\n            dp[1][i][1] = 1\n\n        for i in range(2, n + 1):\n            for j in range(1, 7):\n                for l in range(1, 7):\n                    if l != j:\n                        dp[i][j][1] += sum(dp[i - 1][l]) % kMod\n                    else:\n                        for k in range(1, rollMax[j - 1] + 1):\n                            dp[i][j][k] += dp[i - 1][j][k - 1] % kMod\n\n        temp = sum([(sum(i) % kMod) for i in dp[-1]])\n\n        return int(temp % kMod)\n\n    def dieSimulator_temp(self, n: int, rollMax: List[int]) -> int:\n\n        dp = [[0 for _ in range(7)] for i in range(n+1)]\n        kMod = 1e9 + 7\n        \n        for i in range(1, 7):\n            dp[1][i] = 1\n\n        # steps\n        for i in range(2, n+1):\n\n            # current value\n            for j in range(1, 7):\n\n                k = i-rollMax[j-1]\n\n                # all the posibilities included invalid ones\n                dp[i][j] = sum(dp[i-1])\n\n                # take off invalid posibilities\n                invalid = max(0, k) if k <= 1 else (sum(dp[k-1])-dp[k-1][j])\n                dp[i][j] = ((dp[i][j]-invalid) % kMod+kMod) % kMod\n\n        return int(sum(dp[-1]) % (kMod))\n\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        faces = len(rollMax)\n        # [n + 1][faces + 1] dimensional dp array\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        # initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n            # iterate through each column (face)\n            for j in range(faces):\n                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n            # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007\n        \n        \n                \n", "  \n        \nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        # [n + 1][faces + 1] dimensional dp array\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        # initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n            # iterate through each column (face)\n            for j in range(faces):\n                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n            # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0 for i in range(7)] for j in range(n + 1)]\n        dp[0][6] = 1\n        for j in range(6):\n            dp[1][j] = 1\n        dp[1][6] = 6\n        \n        for i in range(2, n + 1):\n            for j in range(6):\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += dp[i - k][6] - dp[i - k][j]\n            dp[i][6] = sum(dp[i])\n        \n        return dp[n][6] % 1000000007\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        faces = len(rollMax)\n        # [n + 1][faces + 1] dimensional dp array\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        # initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n            # iterate through each column (face)\n            for j in range(faces):\n                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state\n                k = 1\n                while i >= k and k <= rollMax[j]:\n                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n                    k+=1\n            # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007\n        \n        \n                \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dp[i][j][k]\n        dp = [[[0 for _ in range(16)] for _ in range(6)] for _ in range(n + 1)]\n        \n        # dp[i][j][k] = The number of sequences with i rolls when the current roll is j and we've rolled j exactly k consecutive times.\n        \n        for i in range(0, 6):\n            dp[1][i][1] = 1\n        \n        for i in range(2, n + 1):\n            for j in range(0, 6):\n                for k in range(1, rollMax[j] + 1):\n                    if k > i:\n                        continue\n                    \n                    if k == 1:\n                        # The previous roll must have been different.\n                        for l in range(0, 6):\n                            if l == j:\n                                continue\n                            s = int(sum(dp[i - 1][l]) % (1e9 + 7))\n                            dp[i][j][k] += s\n                    else:\n                        # The previous roll must have been the same.\n                        dp[i][j][k] += dp[i - 1][j][k - 1]\n                        \n                    \n        ans = 0\n        for arr in dp[n]:\n            ans = ans + sum(arr)\n        return int(ans % (1e9 + 7))", "#[] DP(bottom-up)\n#O(6N * 6T): T: upperbound of rollMax\n\n#f(i, d): number of combinations of res[0~i] if the last number is d\n#f(i, ?) = 1 if i == 0\n#                 |------------| <= rollMax[d]\n#               d'd d d ... d [d]\n#               ? d'd d ... d [d]\n#               ? ? d'd ... d [d]\n#               ? ? ? d'... d [d]\n#               ? ? ? ? ... d'[d]\n#f(i, d) = sum{ f(j, d') for j in i-rollMax[d] ~ i-1 for d' in 0~5\n#               if i-rollMax[d] >= 0 and d' != d }\n#          sum{ f(i-1, d') for any d' if i < rollMax[d]} < no limit\nMOD = 1000000007\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * 6 for _ in range(n)]\n        for d in range(6):\n            dp[0][d] = 1\n        for i in range(1, n):\n            for d in range(6):\n                if i < rollMax[d]: #no constraint\n                    dp[i][d] = sum(dp[i-1][x] for x in range(6)) % MOD\n                else:\n                    dp[i][d] = sum(dp[j][x] for j in range(i-rollMax[d], i) for x in range(6) if x != d) % MOD\n        return sum(dp[n-1][d] for d in range(6)) % MOD", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        memo = [[0] * 7 for _ in range(n + 1)]\n        for j in range(6):\n            memo[1][j] = 1\n            memo[1][-1] += memo[1][j]\n        for i in range(2, n + 1):\n            for j in range(6):\n                memo[i][j] = memo[i - 1][-1]\n                k = i - rollMax[j]\n                if k == 1: memo[i][j] -= 1\n                elif k > 1: memo[i][j] -= (memo[k - 1][-1] - memo[k - 1][j])\n                memo[i][-1] += memo[i][j]\n        return memo[n][6] % int(1e9 + 7)", "# https://leetcode.com/problems/dice-roll-simulation/discuss/404840/Short-Python-DP-with-detailed-image-explanation\n# \u89e3\u8aac\u898b\u308c\u3070\u308f\u304b\u308b\u3051\u3069\u3001\u96e3\u3057\u3044\n\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        \n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        dp[0][faces] = 1\n        for j in range(faces):\n            dp[1][j] = 1\n        dp[1][faces] = faces\n        \n        for i in range(2, n+1):\n            for j in range(faces):\n                for k in range(1, rollMax[j]+1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += dp[i-k][faces] - dp[i-k][j]\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % (10**9+7)\n        \n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        k={}\n        mod=10**9+7\n        for i in range(6):\n            k[i]=[0 for i in range(rollMax[i])]\n            if k[i]:\n                k[i][-1]=1\n        for i in range(n):\n            su=0\n            temp_su=[0 for j in range(6)]\n            for j in range(6):\n                val=sum(k[j])\n                su+=val\n                temp_su[j]=val\n            for j in range(6):\n                temp=[x for x in k[j]]\n                for x in range(rollMax[j]-1):\n                    temp[x]=k[j][x+1]%mod\n                temp[-1]=su-temp_su[j]%mod\n                k[j]=temp\n        return su%mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        \n        '''\n        https://leetcode.com/problems/dice-roll-simulation/discuss/403756/Java-Share-my-DP-solution\n        \n        num[i,j] = num sequences with i rolls that ends with j\n        \n        num[i,j] = sum_{k\u2260j} (num[i-1,k]) + num[i-1,j] - num[i-rollMax[i],j]\n        '''\n        \n        num = [[1]*6+[6] for i in range(16)]  # rollMax[i] <= 15\n        pointer = 1\n        \n        def idxLast(i):\n            return (pointer - i) % 16\n        \n        for k in range(2,n+1):\n            \n            for j in range(6):\n                \n                if rollMax[j] >= k:\n                    num[idxLast(0)][j] = num[idxLast(1)][-1]\n                \n                else:\n                    num[idxLast(0)][j] = 0\n                    for i in range(1, rollMax[j]+1):\n                        num[idxLast(0)][j] = (num[idxLast(0)][j] + num[idxLast(i)][-1] - num[idxLast(i)][j]) % int(1E9 + 7)\n            \n            num[idxLast(0)][-1] = sum(num[idxLast(0)][:6]) % int(1E9 + 7)\n            \n            pointer += 1\n        \n        # print(num)\n        \n        return num[idxLast(1)][-1] % int(1E9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        # [n + 1][faces + 1] dimensional dp array\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        # initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n            # iterate through each column (face)\n            for j in range(faces):\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0: break \n                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n            # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        face = len(rollMax)\n        \n        dp = [[0 for i in range(face + 1)] for j in range(n + 1)]\n\n        # 0 roll\n        dp[0][face] = 1\n        # 1 roll\n        for f in range(face):\n            dp[1][f] = 1\n        dp[1][face] = 6\n        # 2 roll and more\n\n        for i in range(2, n + 1):\n            for j in range(face):\n                for k in range(1, rollMax[j] + 1):\n                    if (i - k) < 0:\n                        break\n                    dp[i][j] += dp[i - k][face] - dp[i - k][j]\n            dp[i][face] = sum(dp[i])\n        \n        return dp[n][face]%1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0 for _ in range(7)] for _ in range(n+1)]\n        dp[0][6] = 1\n        for j in range(6):\n            dp[1][j] = 1\n        dp[1][6] = sum(dp[1])\n        for i in range(2, n+1):\n            for j in range(6):\n                dp[i][j] = dp[i-1][6]\n                if i - rollMax[j] - 1 >= 0:\n                    dp[i][j] -= dp[i - rollMax[j] - 1][-1] - dp[i - rollMax[j] - 1][j]\n            dp[i][-1] = sum(dp[i])\n        return dp[n][6] % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        dp[0][faces] = 1\n        for j in range(faces):\n            dp[1][j] = 1\n        dp[1][faces] = faces\n        for i in range(2, n + 1):\n            for j in range(faces):\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n            dp[i][faces] = sum(dp[i])\n        return dp[n][faces] % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[] for i in range(6)]\n        new_dp = [[] for i in range(6)]\n        for i in range(6):\n            dp[i].append(1)\n            for j in range(1, rollMax[i]):\n                dp[i].append(0)\n            new_dp[i] = [0 for i in range(rollMax[i])] \n        for r in range(1, n):    \n            for i in range(6):\n                new_dp[i][0] = sum([sum(dp[j]) if j != i else 0 for j in range(6)])\n                for j in range(1, rollMax[i]):\n                    new_dp[i][j] = dp[i][j-1]\n            dp, new_dp = new_dp, dp\n        return sum([sum(x) for x in dp]) % (10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * 6 + [1] for i in range(n + 1)]\n        dp[1] = [1] * 6 + [6] \n        #print(dp)\n        for i in range(2, n+1):\n            for j in range(6):\n                for k in range(1, rollMax[j]+1):\n                    if i - k < 0: break\n                    dp[i][j] += dp[i-k][6] - dp[i-k][j]\n            #print(dp[i])\n            dp[i][6] = sum(dp[i][:-1])\n        #print(dp)\n        return dp[-1][-1] % (10**9+7)\n\n        \n\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * 6 + [1] for i in range(n + 1)]\n        dp[1] = [1] * 6 + [6] \n        for i in range(2, n+1):\n            for j in range(6):\n                for k in range(1, rollMax[j]+1):\n                    if i - k < 0: break\n                    dp[i][j] += dp[i-k][6] - dp[i-k][j]\n            dp[i][6] = sum(dp[i][:-1])\n        return dp[-1][-1] % (10**9+7)\n\n        \n\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        if n == 0:\n            return 0\n        hist = [[0 for _ in range(rollMax[i])] for i in range(6)]\n        for i in range(6):\n            hist[i][0] = 1\n        \n        for i in range(n-1):\n            new = [[0 for _ in range(rollMax[i])] for i in range(6)]\n            for j in range(6):\n                s = sum(sum(e) for idx, e in enumerate(hist) if idx != j)\n                new[j][0] = s\n                for rep in range(1, rollMax[j]):\n                    new[j][rep] = hist[j][rep-1]\n            hist = new\n        \n        return sum(sum(e) for e in hist) % (1000000007)", "# from copy import deepcopy\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0 for _ in range(i)] for i in rollMax]\n        \n        def sum_dp(j = -1):\n            return sum(sum(x) for index, x in enumerate(dp) if index != j)\n        \n        for i in range(6):\n            dp[i][0] = 1\n        \n        # print(dp)\n        for i in range(n-1):\n            dp2 = [[0 for _ in range(i)] for i in rollMax]\n            for j in range(6):\n                max_len = len(dp[j])\n                for k in range(max_len-1, 0, -1):\n                    dp2[j][k] = dp[j][k-1]\n                dp2[j][0] = sum_dp(j)\n            dp = dp2\n        \n        # print(dp)\n        return sum_dp() % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        dp =collections.deque([[0] * 6 for i in range(max(rollMax))])\n        dp[0] = [1] * 6\n        for i in range(2,  n + 1):\n            dp2 = [0]  * 6\n            for j in range(6):\n                if rollMax[j] >= i:\n                    dp2[j] = 1\n                for k in range(min(rollMax[j], i)):\n                    for d in range(6):\n                        if d == j:\n                            continue\n                        dp2[j] = (dp2[j] + dp[k][d]) % MOD\n            dp.pop()\n            dp.appendleft(dp2)\n        return sum(dp[0]) % MOD\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dynamic programming\n        # dp[i][j]: num of seqs for i + 1 rolls that ends at face j + 1\n        dp = [[0 for c in range(6)] for r in range(n)]\n        # initialize\n        for c in range(6):\n            dp[0][c] = 1\n        # fill in dp by rows\n        for r in range(1, n):\n            for c in range(6):\n                if r < rollMax[c]:\n                    dp[r][c] = sum(dp[r-1])\n                else:\n                    for prev in range(r - rollMax[c], r):\n                        dp[r][c] += sum(dp[prev]) - dp[prev][c]\n        return sum(dp[-1]) % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        dp =collections.deque([[0] * 7 for i in range(max(rollMax))])\n        dp[0] = [1] * 7\n        for i in range(1,  n + 1):\n            dp2 = [0]  * 7\n            for j in range(7):\n                for d in range(6):\n                    if d == j:\n                        continue\n                    for k in range(min(rollMax[d], i)):\n                        dp2[j] = (dp2[j] + dp[k][d]) % MOD\n            dp.pop()\n            dp.appendleft(dp2)\n        return dp[0][6]\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n             dp=[[0]*7 for i in range(n+1)]\n             dp[0][-1]=1\n             for j in range(6):\n                dp[1][j]=1\n             dp[1][-1]=6\n             for i in range(2,n+1):\n                  for j in range(6):\n                     dp[i][j]=dp[i-1][-1]\n                     k=i-rollMax[j]-1\n                     if k>=0:\n                        dp[i][j]-=(dp[k][-1]-dp[k][j])\n                     dp[i][-1]+=dp[i][j]\n             return dp[-1][-1]%int(1e9+7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10**9 + 7\n        dp = [[0, 1] + [0] * 15 for i in range(6)]\n        for _ in range(n - 1):\n            dp2 = [[0] * 17 for i in range(6)]\n            for i in range(6):\n                for k in range(1, rollMax[i] + 1):\n                    for j in range(6):\n                        if i == j:\n                            if k < rollMax[i]:\n                                dp2[j][k + 1] += dp[i][k] % mod\n                        else:\n                            dp2[j][1] += dp[i][k] % mod\n            dp = dp2\n        return sum(sum(row) for row in dp) % mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        dp =collections.deque([[0] * 7 for i in range(max(rollMax))])\n        dp[0] = [1] * 7\n        for i in range(1,  n + 1):\n            dp2 = [0]  * 7\n            for j in range(7):\n                for d in range(6):\n                    if d == j:\n                        continue\n                    for k in range(min(rollMax[d], i)):\n                        dp2[j] = (dp2[j] + dp[k][d]) % MOD\n            dp.pop()\n            dp.appendleft(dp2)\n        # print(dp)\n        return dp[0][6] % MOD\n#         @lru_cache(None)\n#         def roll(j, i):\n#             if i == 0:\n#                 return 1\n#             cnt = 0\n#             for d in range(6):\n#                 if d != j:\n#                     for k in range(min(rollMax[d], i)):\n#                         cnt = (cnt + roll(d, i - k - 1)) % MOD\n#             return cnt\n        \n#         return roll(-1, n)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        p = 10**9 + 7\n        C = [[[0 for v in range(rollMax[i])] for i in range(6)] for k in range(n)]\n        for i in range(6):\n            C[0][i][0] = 1\n        for k in range(n-1):\n            A = {}\n            for i in range(6):\n                for v in range(rollMax[i]-1):\n                    A[(i,v+1)] = C[k][i][v]\n                A[(i,0)] = sum([C[k][i1][v] for i1 in range(6) for v in range(rollMax[i1]) if i1!=i])\n            for i in range(6):\n                for v in range(rollMax[i]):\n                    C[k+1][i][v] = A[(i,v)]%p\n#        print(C)\n        return(sum([sum(row) for row in C[-1]])%p)", "class Solution:\n    def dieSimulator(self, n, rollMax):\n        mod = 10**9 + 7\n        dp = [[0, 1] + [0] * 15 for i in range(6)]\n        for _ in range(n - 1):\n            dp2 = [[0] * 17 for i in range(6)]\n            for i in range(6):\n                for k in range(1, rollMax[i] + 1):\n                    for j in range(6):\n                        if i == j:\n                            if k < rollMax[i]:\n                                dp2[j][k + 1] += dp[i][k] % mod\n                        else:\n                            dp2[j][1] += dp[i][k] % mod\n            dp = dp2\n        return sum(sum(row) for row in dp) % mod", "class Solution:\n    def dieSimulator(self, n, rollMax):\n        mod = 10**9 + 7\n        dp = [[0, 1] + [0] * 15 for i in range(6)]\n        for _ in range(0, n - 1):\n            dp2 = [[0] * 17 for i in range(0,6)]\n            for i in range(6):\n                for k in range(1, rollMax[i] + 1):\n                    for j in range(6):\n                        if i == j:\n                            if k < rollMax[i]:\n                                dp2[j][k + 1] += dp[i][k] % mod\n                        else:\n                            dp2[j][1] += dp[i][k] % mod\n            dp = dp2\n        return sum(sum(row) for row in dp) % mod\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dp[i][k] means after several rolls, the number of sequence that ends with k times i.\n        mod = 10**9 + 7\n        dp = [[0, 1] + [0] * 14 for i in range(6)]\n        for _ in range(n - 1):\n            dp2 = [[0] * 16 for i in range(6)]\n            for i in range(6):\n                for k in range(1, rollMax[i] + 1):\n                    for j in range(6):\n                        if i == j:\n                            if k < rollMax[i]:\n                                dp2[j][k + 1] += dp[i][k] % mod\n                        else:\n                            dp2[j][1] += dp[i][k] % mod\n            dp = dp2\n        return sum(sum(row) for row in dp) % mod\n        \n        \n        \n        \n        # mod = 10**9 + 7\n        # dp = [[0, 1] + [0] * 15 for i in range(6)]\n        # for _ in range(n - 1):\n        #     dp2 = [[0] * 17 for i in range(6)]\n        #     for i in range(6):\n        #         for k in range(1, rollMax[i] + 1):\n        #             for j in range(6):\n        #                 if i == j:\n        #                     if k < rollMax[i]:\n        #                         dp2[j][k + 1] += dp[i][k] % mod\n        #                 else:\n        #                     dp2[j][1] += dp[i][k] % mod\n        #     dp = dp2\n        # return sum(sum(row) for row in dp) % mod\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        @lru_cache(None)\n        def roll(j, i):\n            if i == 0:\n                return 1\n            if i < 0:\n                return 0\n            cnt = 0\n            for d in range(6):\n                if d != j:\n                    for k in range(rollMax[d]):\n                        cnt = (cnt + roll(d, i - k - 1)) % MOD\n            return cnt\n        \n        return roll(-1, n)", "class Solution:\n    def dieSimulator(self, n, rollMax):\n        mod = 10**9 + 7\n        dp = [[0, 1] + [0] * 15 for i in range(6)]\n        for _ in range(n - 1):\n            dp2 = [[0] * 17 for i in range(6)]\n            for i in range(6):\n                for k in range(1, rollMax[i] + 1):\n                    for j in range(6):\n                        if i == j:\n                            if k < rollMax[i]:\n                                dp2[j][k + 1] += dp[i][k] % mod\n                        else:\n                            dp2[j][1] += dp[i][k] % mod\n            dp = dp2\n        return sum(sum(row) for row in dp) % mod\n#     def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n#         faces = len(rollMax)\n#         # [n + 1][faces + 1] dimensional dp array\n#         dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n#         # initialization\n#         # roll 0 times, the total combination is 1\n#         dp[0][faces] = 1\n#         # roll 1 times, the combinations that end at face j is 1\n#         for j in range(faces):\n#             dp[1][j] = 1\n#         # roll 1 times, the total combination is faces = 6\n#         dp[1][faces] = faces\n        \n#         # then roll dices from 2 times, until n times\n#         for i in range(2, n + 1):\n#             # iterate through each column (face)\n#             for j in range(faces):\n#                 # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state\n#                 dp[i][j] = dp[i-1][faces]\n#                 if i-1-rollMax[j] >= 0:\n#                     dp[i][j] -= (dp[i-1-rollMax[j]][faces] - dp[i-1-rollMax[j]][j])\n#             # update total sum of this row\n#             dp[i][faces] = sum(dp[i])\n        \n#         return dp[n][faces] % 1000000007\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        # [n + 1][faces + 1] dimensional dp array\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        # initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n            # iterate through each column (face)\n            for j in range(faces):\n                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state\n                dp[i][j] = dp[i-1][faces]\n                if i-1-rollMax[j] >= 0:\n                    dp[i][j] -= (dp[i-1-rollMax[j]][faces] - dp[i-1-rollMax[j]][j])\n            # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [ [0 for _ in range(7)] for _ in range(n+1) ]\n        dp[1] = [0] + [1 for _ in range(1, 7)]\n        mod = 10**9+7\n        \n        for i in range(2, n+1):\n            for j in range(1, 7):\n                for k in range(1, rollMax[j-1]+1):\n                    if i-k > 0:\n                        dp[i][j] += sum(dp[i-k]) - dp[i-k][j]\n                    if i-k == 0:\n                        dp[i][j] += 1\n        \n        return sum(dp[n])%mod\n        \n", "from typing import List\nimport collections\nimport heapq\nimport itertools\nimport bisect\nimport copy\nimport random\nimport re\nimport fractions\nimport math\n\nmod = 10 ** 9 + 7\n\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n\n        rollMax = [0] + rollMax\n        dp = [[0, 1] + [0] * 15 for _ in range(7)]\n\n        for _ in range(2, n + 1):\n            dp2 = [[0] * 17 for _ in range(7)]\n            for i in range(1, 7):\n                for j in range(1, 7):\n                    for k in range(1, rollMax[j] + 1):  # we could extend j no more\n                        if i == j:\n                            if k < rollMax[i]:\n                                dp2[i][k + 1] += dp[i][k] % mod\n                        else:\n                            dp2[i][1] += dp[j][k] % mod\n\n            dp = dp2\n\n        return sum(map(sum, dp)) % mod\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        @lru_cache(None)\n        def roll(i, j):\n            if i == 0:\n                return 1\n            if i < 0:\n                return 0\n            cnt = 0\n            for d in range(6):\n                if d != j:\n                    for k in range(rollMax[d]):\n                        cnt = (cnt + roll(i - k - 1, d)) % MOD\n            return cnt\n        \n        return roll(n, -1)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10**9 + 7\n        dp = [[0, 1] + [0] * 15 for _ in range(6)]\n        for _ in range(n - 1):\n            dp2 = [[0] * 17 for _ in range(6)]\n            for i in range(6):\n                for k in range(1, rollMax[i] + 1):\n                    for j in range(6):\n                        if j == i:\n                            if k < rollMax[i]:\n                                dp2[j][k + 1] += dp[i][k] % mod\n                        else:\n                            dp2[j][1] += dp[i][k] % mod\n            dp = dp2\n        return sum(sum(d) for d in dp) % mod\n            \n", "from functools import lru_cache\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10**9+7\n        @lru_cache\n        def roll(i, j):\n            # print(i, j)\n            if i == 0:\n                return 1\n\n            ans = 0\n            for dice in range(6):\n                if dice == j: \n                    continue\n                \n                for k in range(1, min(rollMax[dice], i)+1):\n                    # print('roll', dice, k, i-k)\n                    ans += roll(i-k, dice)\n                    ans %= MOD\n            return ans % MOD\n        \n        return roll(n, -1)\n                \n    \n# class Solution:\n#     def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n#         dp = [[0] * 6 for _ in range(n+1)]\n#         dp[1] = [1] * 6\n#         # print(dp[1])\n        \n#         for i in range(2, n+1):\n#             for j in range(6):\n#                 pi = i - rollMax[j]\n#                 if pi < 1:\n#                     dp[i][j] = sum(dp[i-1])\n#                 elif pi == 1:\n#                     dp[i][j] = sum(dp[i - 1]) - 1\n#                 elif pi > 1:\n#                     dp[i][j] = sum(dp[i - 1]) - sum(dp[pi-1][:j] + dp[pi-1][j + 1:]) \n#                 dp[i][j] = dp[i][j] % (10**9 + 7)\n#             # print(dp[i])\n#         return sum(dp[-1]) % (10**9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dp[i][k] means after several rolls, the number of sequence that ends with i for k times.\n        mod = 10**9 + 7\n        dp = [[0, 1] + [0] * 14 for i in range(6)]\n        for _ in range(n - 1):\n            dp2 = [[0] * 16 for i in range(6)]\n            # update the dp table\n            for i in range(6):\n                for k in range(1, rollMax[i] + 1):\n                    # all choices\n                    for j in range(6):\n                        # if same, only not > max\n                        if i == j:\n                            if k < rollMax[i]:\n                                dp2[j][k + 1] += dp[i][k] % mod\n                        # if not, add anyway\n                        else:\n                            dp2[j][1] += dp[i][k] % mod\n            dp = dp2\n        return sum(sum(row) for row in dp) % mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        @lru_cache(None)\n        def roll(j, i):\n            if i == 0:\n                return 1\n            if i < 0:\n                return 0\n            cnt = 0\n            for d in range(6):\n                if d != j:\n                    for k in range(min(rollMax[d], i)):\n                        cnt = (cnt + roll(d, i - k - 1)) % MOD\n            return cnt\n        \n        return roll(-1, n)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        @lru_cache(None)\n        def roll(j, i):\n            if i == 0:\n                return 1\n            cnt = 0\n            for d in range(6):\n                if d != j:\n                    for k in range(min(rollMax[d], i)):\n                        cnt = (cnt + roll(d, i - k - 1)) % MOD\n            return cnt\n        \n        return roll(-1, n)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        mod = 10**9 + 7\n        dp = [[0, 1] + [0] * 14 for i in range(6)]\n        for _ in range(n - 1):\n            dp2 = [[0] * 16 for i in range(6)]\n            for i in range(6):\n                for k in range(1, rollMax[i] + 1):\n                    for j in range(6):\n                        if i == j:\n                            if k < rollMax[i]:\n                                dp2[j][k + 1] += dp[i][k] % mod\n                        else:\n                            dp2[j][1] += dp[i][k] % mod\n            dp = dp2\n        return sum(sum(row) for row in dp) % mod\n    \n    \n        M, K = 6, 15\n        dp = [[[0]*(K + 1) for _ in range(M + 1)] for _ in range(n + 1)]\n        \n        for i in range(1, M+1):\n            dp[1][i][1] = 1\n            \n        for i in range(2, n+1):           \n            for j in range(1, M+1):                  \n                for m in range(1, M+1):\n                    if m != j:\n                        dp[i][j][1] += sum(dp[i-1][m][h] for h in range(1, rollMax[m-1] + 1))\n\n                for k in range(1, K):                  \n                    dp[i][j][k+1] += dp[i-1][j][k]   \n                \n        ans = 0\n        for m in range(1, M+1):\n            for k in range(1, rollMax[m-1] + 1):\n                ans += dp[-1][m][k]\n                \n        return ans % (10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        mod = 10**9 + 7\n        dp = [[0, 1] + [0] * 15 for i in range(6)]\n        for _ in range(n - 1):\n            dp2 = [[0] * 17 for i in range(6)]\n            for i in range(6):\n                for k in range(1, rollMax[i] + 1):\n                    for j in range(6):\n                        if i == j:\n                            if k < rollMax[i]:\n                                dp2[j][k + 1] += dp[i][k] % mod\n                        else:\n                            dp2[j][1] += dp[i][k] % mod\n            dp = dp2\n        return sum(sum(row) for row in dp) % mod\n    \n    \n        M, K = 6, 15\n        dp = [[[0]*(K + 1) for _ in range(M + 1)] for _ in range(n + 1)]\n        \n        for i in range(1, M+1):\n            dp[1][i][1] = 1\n            \n        for i in range(2, n+1):           \n            for j in range(1, M+1):                  \n                for m in range(1, M+1):\n                    if m != j:\n                        dp[i][j][1] += sum(dp[i-1][m][h] for h in range(1, rollMax[m-1] + 1))\n\n                for k in range(1, K):                  \n                    dp[i][j][k+1] += dp[i-1][j][k]   \n                \n        ans = 0\n        for m in range(1, M+1):\n            for k in range(1, rollMax[m-1] + 1):\n                ans += dp[-1][m][k]\n                \n        return ans % (10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        # [n + 1][faces + 1] dimensional dp array\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        # initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n            # iterate through each column (face)\n            for j in range(faces):\n                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state\n                dp[i][j] = dp[i-1][faces]\n                if i-1-rollMax[j] >= 0:\n                    dp[i][j] -= (dp[i-1-rollMax[j]][faces] - dp[i-1-rollMax[j]][j])\n                # for k in range(1, rollMax[j] + 1):\n                #     if i - k < 0:\n                #         break\n                #     dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n            # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dp[i][j][k]: after ith throw, the number of sequences which end with j (j in [0,5]) and continous k times (k in [1,15])\n        dp = [[[0]*(max(rollMax)+1) for _ in range(6)] for _ in range(n)]\n        mod = 10**9 + 7\n        for j in range(6):\n            dp[0][j][1] = 1\n        for i in range(1,n):\n            for j in range(6):\n                for k in range(1,min(rollMax[j]+1,i+2)):\n                    if k == 1:\n                        for prevj in range(6):\n                            if prevj != j:\n                                dp[i][j][k] += sum(dp[i-1][prevj])\n                    else:\n                        dp[i][j][k] = dp[i-1][j][k-1] \n        return sum([sum(dp[-1][j]) for j in range(6)]) % mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        F = [[0 for i in range(6)] for i in range(n + 1)]\n        sumF = [0 for i in range(n + 1)]\n        for i in range(6):\n            F[1][i] = 1\n        sumF[0] = 6\n        MOD = 10**9 + 7\n        for i in range(2, n + 1):\n            for j in range(6):\n                for p in range(1, rollMax[j] + 1):\n                    if i == p:\n                        F[i][j] = (F[i][j] + 1) % MOD\n                        continue\n                    for k in range(6):\n                        if j == k: continue\n                        if i > p:\n                            F[i][j] = (F[i][j] + F[i - p][k]) % MOD\n\n        res = 0\n        for i in range(6):\n            res = (res + F[n][i]) % MOD\n            # print(F[n][i])\n        return round(res)\n        \n        #1(11), 2(11), 3(11), 4(11), 5(11), 6(11) -> 6\n        #1(22), 2(22), 3(22), 4(22), 5(22), 6(22) -> 6\n        #1(33), 2(33), 3(33), 4(33), 5(33), 6(33) -> 6\n        #\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # Idea:\n        # 1. Divide and conquer with substructure where:\n        #       numRolls(n) = sum(numRolls(n - i) * 5) where 1 <= i <= rollMax[i]\n        #\n        #    given that number of sequences with length N ending at X is sum of:\n        #       number of sequences with length N - 1 ending at non-X\n        #       number of sequences with length N - 2 ending at non-X\n        #       ...\n        #       number of sequences with length N - C ending at non-X\n        #\n        #    where C is number of repeats from which its not allowed\n        #\n        # 2. Memorization\n        #\n        # Time: O(NM) where N is length of sequence, M is max repeat\n\n        memo = [[0] * 6 for _ in range(n)] # memo[n][x] number of sequences of length n ending at x\n        # General cases:\n        for i in range(n):\n            for x in range(6):\n                # Sequence with length i ending at x\n                maxRolls = rollMax[x]\n                for j in range(i - 1, i - 1 - maxRolls, -1):\n                    # Sequence with length j ending at non-x\n                    if j == -1:\n                        memo[i][x] += 1\n                        break\n\n                    for y in range(6):\n                        if y != x: memo[i][x] += memo[j][y]\n\n        return sum(memo[-1]) % (10 ** 9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # Idea:\n        # 1. DP with optimal substructure where:\n        #       number of sequences with length N ending at X is sum of:\n        #           number of sequences with length N - 1 ending at non-X\n        #           number of sequences with length N - 2 ending at non-X\n        #           ...\n        #           number of sequences with length N - C ending at non-X\n        #\n        #       where C is number of repeats from which its not allowed\n        #\n        # Time: O(NM) where N is length of sequence, M is max repeat\n\n        memo = [[0] * 6 for _ in range(n)] # memo[n][x] number of sequences of length n ending at x\n        # General cases:\n        for i in range(n):\n            for x in range(6):\n                # Sequence with length i ending at x\n                maxRolls = rollMax[x]\n                for j in range(i - 1, i - 1 - maxRolls, -1):\n                    # Base cases:\n                    if j == -1:\n                        memo[i][x] += 1\n                        break\n\n                    # Sequence with length j ending at non-x\n                    for y in range(6):\n                        if y != x: memo[i][x] += memo[j][y]\n\n        return sum(memo[-1]) % (10 ** 9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # Idea:\n        #   DP with optimal substructure where:\n        #       number of sequences of length N ending at X is sum of:\n        #           number of sequences of length N - 1 ending at non-X (also seq of len N ending with X)\n        #           number of sequences of length N - 2 ending at non-X (also seq of len N ending with XX)\n        #           ...\n        #           number of sequences of length N - C ending at non-X (also seq of len N ending with XX...X)\n        #\n        #       where C is number of max repeats\n        #\n        # Time: O(NM) where N is length of sequence, M is max repeat\n\n        memo = [[0] * 6 for _ in range(n)] # memo[n][x] number of sequences of length n ending at x\n        # General cases:\n        for i in range(n):\n            for x in range(6):\n                # Sequence with length i ending at x\n                maxRepeats = rollMax[x]\n                for j in range(i - 1, i - 1 - maxRepeats, -1):\n                    # Base cases:\n                    if j == -1:\n                        memo[i][x] += 1\n                        break\n\n                    # Sequence with length j ending at non-x\n                    for y in range(6):\n                        if y != x: memo[i][x] += memo[j][y]\n\n        return sum(memo[-1]) % (10 ** 9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[[0] * (max(rollMax) + 1) for _ in range(6)] for _ in range(n)]\n        for i in range(6):\n            dp[0][i][1] = 1\n        mod = 1000000007\n        for i in range(n-1):\n            for d in range(6):\n                for pre in range(6):\n                    if pre == d:\n                        for cnt in range(rollMax[pre]):\n                            dp[i+1][d][cnt + 1] += dp[i][pre][cnt] % mod\n                    else:\n                        for cnt in range(rollMax[pre] + 1):\n                            dp[i+1][d][1] += dp[i][pre][cnt] % mod\n        return sum([sum(x) for x in dp[-1]]) % mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[[0] * (max(rollMax) + 1) for _ in range(6)] for _ in range(2)]\n        for i in range(6):\n            dp[0][i][1] = 1\n        mod = 1000000007\n        for i in range(n-1):\n            idx = i % 2\n            dp[1-idx] = [[0] * (max(rollMax) + 1) for _ in range(6)]\n            for d in range(6):\n                for pre in range(6):\n                    if pre == d:\n                        for cnt in range(rollMax[pre]):\n                            \n                            dp[1-idx][d][cnt + 1] += dp[idx][pre][cnt] % mod\n                    else:\n                        for cnt in range(rollMax[pre ] + 1):\n                            dp[1-idx][d][1] += dp[idx][pre][cnt] % mod\n        return sum([sum(x) for x in dp[1-n%2]]) % mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dp[i][j][k]: after ith throw, the number of sequences which end with j (j in [0,5]) and continous k times (k in [1,15])\n        dp = [[[0]*16 for _ in range(6)] for _ in range(n)]\n        mod = 10**9 + 7\n        for j in range(6):\n            dp[0][j][1] = 1\n        for i in range(1,n):\n            for j in range(6):\n                for k in range(1,min(rollMax[j]+1,i+2)):\n                    if k == 1:\n                        for prevj in range(6):\n                            if prevj != j:\n                                dp[i][j][k] += sum(dp[i-1][prevj])\n                    else:\n                        dp[i][j][k] = dp[i-1][j][k-1] \n        return sum([dp[-1][j][k] for j in range(6) for k in range(16)]) % mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        def init():\n            return [[0 for _ in range(20)] for _ in range(7)]\n        st = init()\n        pst = init()\n        for i in range(1, 7):\n            pst[i][1] = 1\n            \n        for _ in range(1, n):\n            for i in range(1, 7):\n                st[i][1] = 0\n                for j in range(1, 7):\n                    if i != j:\n                        st[i][1] += sum(pst[j])\n                for j in range(2, rollMax[i - 1] + 1):\n                    st[i][j] = pst[i][j - 1] % 1000000007\n            st, pst = pst, st\n        return sum([sum(r) for r in pst]) % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n#         self.rollMax = tuple(rollMax)\n        \n#         @lru_cache(None)\n#         def helper(n, ban):\n#             times = 0\n#             if n == 1:\n#                 for t in ban:\n#                     if t > 0:\n#                         times += 1\n#                 return times\n\n#             for i, t in enumerate(ban):\n#                 if t > 0:\n#                     cur = tuple()\n#                     for j in range(len(ban)):\n#                         if i == j:\n#                             cur += (ban[j]-1,)\n#                         else:\n#                             cur += (self.rollMax[j], )\n#                     times += helper(n-1, cur)\n\n#             return times % (10**9 + 7)\n        \n#         return helper(n, tuple(rollMax))\n        dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]\n        for j in range(len(rollMax)):\n            dp[1][j] = 1\n            dp[1][-1] += dp[1][j]\n        \n        for i in range(2, n + 1):\n            for j in range(len(rollMax)):\n                dp[i][j] = dp[i - 1][-1]\n                k = i - rollMax[j]\n                if k == 1:\n                    dp[i][j] -= 1\n                elif k > 1:\n                    dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])\n                dp[i][-1] += dp[i][j]\n        return dp[n][len(rollMax)] % int(1e9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        def init():\n            return [[0 for _ in range(20)] for _ in range(7)]\n        st = init()\n        pst = init()\n        for i in range(1, 7):\n            pst[i][1] = 1\n            \n        for _ in range(1, n):\n            for i in range(1, 7):\n                st[i][1] = 0\n                for j in range(1, 7):\n                    if i != j:\n                        st[i][1] += sum(pst[j])\n                for j in range(2, rollMax[i - 1] + 1):\n                    st[i][j] = pst[i][j - 1]\n            st, pst = pst, st\n        return sum([sum(r) for r in pst]) % 1000000007", "from functools import lru_cache\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        if n < 1:\n            return 0\n        \n        @lru_cache(maxsize=None)\n        def backtrack(prev_roll, count, seq_len):\n            if seq_len == n:\n                return 1\n\n            result = 0\n\n            for num in range(6):\n                if num != prev_roll:\n                    result += backtrack(num, 1, seq_len+1)\n                elif count < rollMax[num]:\n                    result += backtrack(num, count+1, seq_len+1)\n\n            return result % MOD\n        \n        MOD = (10 ** 9) + 7\n        return backtrack(-1, 0, 0)\n", "from typing import List\nimport collections\nimport heapq\nimport itertools\nimport bisect\nimport copy\nimport random\nimport re\nimport fractions\nimport math\n\nmod = 10 ** 9 + 7\n\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n\n        rollMax = [0] + rollMax\n        dp = [[[0] * 17 for _ in range(7)] for _2 in range(n)]\n        dp[0] = [[0, 1] + [0] * 15 for _ in range(7)]\n\n        for m in range(1, n):\n            for i in range(1, 7):\n                for j in range(1, 7):\n                    for k in range(1, rollMax[j] + 1):  # we could extend j no more\n                        if i == j:\n                            if k < rollMax[i]:\n                                dp[m][i][k + 1] += dp[m-1][i][k] % mod\n                        else:\n                            dp[m][i][1] += dp[m-1][j][k] % mod\n\n\n        return sum(map(sum, dp[n-1])) % mod\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10**9 + 7\n        # dp[i][j] records the value of sequence of i elements with j being the last element\n        dp = [[0]*7 for _ in range(n+1)]\n        # initialize\n        dp[0][0] = 1\n        for i in range(1,7):\n            dp[1][i] = 1\n        for i in range(2,n+1):\n            for j in range(1,7):\n                for z in range(7):\n                    if j==z:\n                        continue\n                    for k in range(1,min(rollMax[j-1],i)+1):\n                        dp[i][j] += dp[i-k][z]\n                        dp[i][j] %= mod\n        return sum([dp[n][i] for i in range(1,7)])%mod\n            \n", "MOD = 1000000007\nclass Solution:\n    def dieSimulator(self, n, rollMax):\n        r = max(rollMax)\n        dp = [[0] * (r + 1) for _ in range(6)]\n        # dp[i][j] last roll was i and i was thrown j consecutive times\n        for i in range(6):\n            dp[i][1] = 1\n        for _ in range(n - 1):\n            tmp = [[0] * (r + 1) for _ in range(6)]\n            for i in range(6):\n                for j in range(6):\n                    if i != j:\n                        for k in range(rollMax[i] + 1):\n                            tmp[j][1] += dp[i][k]\n                    else:\n                        for k in range(rollMax[i]):\n                            tmp[j][k + 1] += dp[j][k]\n                   \n            dp = tmp\n        res = 0\n        for j in range(6):\n            for k in range(r + 1):\n                res = (res + dp[j][k]) % MOD\n        return res % MOD", "MOD = 1000000007\nclass Solution:\n    def dieSimulator(self, n, rollMax):\n        r = max(rollMax)\n        dp = [[0] * (r + 1) for _ in range(6)]\n        # dp[i][j] last roll was i and i was thrown j consecutive times\n        for i in range(6):\n            dp[i][1] = 1\n        for _ in range(n - 1):\n            tmp = [[0] * (r + 1) for _ in range(6)]\n            for i in range(6):\n                for j in range(6):\n                    if i != j:\n                        for k in range(rollMax[i] + 1):\n                            tmp[j][1] += dp[i][k]\n                    else:\n                        for k in range(rollMax[i]):\n                            tmp[j][k + 1] += dp[j][k]\n            dp = tmp\n        return sum(dp[j][k] for j in range(6) for k in range(r + 1)) % MOD", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]\n        for j in range(len(rollMax)):\n            dp[1][j] = 1\n            dp[1][-1] += dp[1][j]\n        \n        for i in range(2, n + 1):\n            for j in range(len(rollMax)):\n                dp[i][j] = dp[i - 1][-1]\n                k = i - rollMax[j]\n                if k == 1:\n                    dp[i][j] -= 1\n                elif k > 1:\n                    dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])\n                dp[i][-1] += dp[i][j]\n        return dp[n][len(rollMax)] % int(1e9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        table = [[0 for i in range(n+1)] for j in range(7)]\n        \n        def helper( n: int, rollMax: List[int], last: int ) -> int:\n            if n==0:\n                return 1\n            if table[last][n] > 0:\n                return table[last][n]\n            \n            total = 0\n            for i in range(1,7):\n                if i==last:\n                    continue\n                for j in range(1,rollMax[i-1]+1):\n                    if j > n:\n                        break\n                    total += helper(n-j, rollMax, i)\n            table[last][n] = total%1000000007\n            return total%1000000007\n        \n        ans = helper(n, rollMax, -1)\n        print(table)\n        \n        return table[-1][-1]", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[[0] * 16 for _ in range(6)] for _ in range(n+1)]\n        MOD = 10 ** 9 + 7\n        for i in range(6):\n            dp[1][i][1] = 1\n            \n        for i in range(2, n+1):\n            for j in range(6):\n                for p in range(6):\n                    for k in range(1, rollMax[p]+1):\n                        if j != p:\n                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k]) % MOD\n                        elif k < rollMax[j]:\n                            dp[i][j][k+1] = dp[i-1][j][k]\n        ans = 0\n        for i in range(6):\n            for k in range(1, rollMax[i]+1):\n                ans = (ans + dp[n][i][k]) % MOD\n        return ans\n        \n", "class Solution:\n    def dieSimulator(self, n, rollMax):\n        K = max(rollMax)\n        dp = [[[0 for k in range(K)] for j in range(6)] for i in range(n)] \n        for j in range(6): dp[0][j][0] = 1\n        for i in range(1, n):\n            for j in range(6):\n                dp[i][j][0] += sum(dp[i-1][t][k] for t in range(6) for k in range(rollMax[t]) if t != j)\n                for k in range(1, min(rollMax[j],i+1)):\n                    dp[i][j][k] = dp[i-1][j][k-1]\n        return sum(dp[n-1][j][k] for j in range(6) for k in range(K)) % (10**9+7)\n    \n    \n    #https://leetcode.com/problems/dice-roll-simulation/discuss/403862/Python-O(N)-Bottom-Up-DP-with-explaination\n", "class Solution:\n    def dieSimulator(self, n, rollMax):\n        K = max(rollMax)\n        dp = [[[0 for _ in range(K)] for _ in range(6)] for _ in range(n)] \n        for j in range(6): dp[0][j][0] = 1\n        for i in range(1, n):\n            for j in range(6):\n                dp[i][j][0] += sum(dp[i-1][t][k] for t in range(6) for k in range(rollMax[t]) if t != j)\n                for k in range(1, min(rollMax[j],i+1)):\n                    dp[i][j][k] = dp[i-1][j][k-1]\n        return sum(dp[n-1][j][k] for j in range(6) for k in range(K)) % (10**9+7)\n    \n    \n    #https://leetcode.com/problems/dice-roll-simulation/discuss/403862/Python-O(N)-Bottom-Up-DP-with-explaination\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        modulo = 10**9 + 7\n        dp = [[0 for _ in range(6)] for _ in range(n)]\n        \n        for roll in range(n):\n            for number in range(6):\n                for limit in range(1, rollMax[number]+1):\n                    if roll >= limit:\n                        for possibility in range(6):\n                            if possibility != number:\n                                dp[roll][number] = (dp[roll][number] + dp[roll-limit][possibility])%modulo\n                    else:\n                        dp[roll][number] += 1\n                        break\n                \n    \n        return sum(dp[n-1])%modulo", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]\n        for j in range(len(rollMax)):\n            dp[1][j] = 1\n            dp[1][-1] += dp[1][j]\n        \n        for i in range(2, n + 1):\n            for j in range(len(rollMax)):\n                dp[i][j] = dp[i - 1][-1]\n                k = i - rollMax[j]\n                if k == 1:\n                    dp[i][j] -= 1\n                elif k > 1:\n                    dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])\n                dp[i][-1] += dp[i][j]\n        return dp[n][len(rollMax)] % int(1e9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        maxAns = 10**9 + 7\n        krollMax = 15\n        \n        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]\n        # [n+1][6][15+1]\n        \n        for i in range(6):\n            dp[1][i][1] = 1\n        \n        for i in range(2,n+1):\n            for j in range(6):#current dice num\n                for p in range(6): # previous dice num \n                    for k in range(1, rollMax[p]+1):\n                        # if k>rollMax[p]: continue\n                        if j != p: #different than previous dice\n                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns\n                        elif k<rollMax[j]:\n                            dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns\n                    # for k in range(1, krollMax+1):\n                    #     if k>rollMax[p]: continue\n                    #     if j != p: #different than previous dice\n                    #         dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns\n                    #     elif k<rollMax[j]:\n                    #         dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns\n        ans = 0\n        for i in range(6):\n            for j in range(rollMax[i]+1):\n                ans += dp[n][i][j]\n        return ans % maxAns\n                            \n                    \n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 7 + 1e9\n        @lru_cache(maxsize=None)\n        def helper(idx, roll, turn):\n            if roll > rollMax[idx]:\n                return 0\n\n            if turn == n:\n                return 1\n\n            result = 0\n            if idx == -1:\n                for i in range(len(rollMax)):\n                    result = (result + helper(i, 1, turn + 1)) % MOD\n            else:\n                for i in range(len(rollMax)):\n                    if i == idx:\n                        result = (result + helper(i, roll + 1, turn + 1)) % MOD\n                    else:\n                        result = (result + helper(i, 1, turn + 1)) % MOD\n            return result\n\n        return int(helper(-1, 0, 0) % MOD)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * 7 for _ in range(n+1)]\n        dp[1][1:] = [1] * 6\n        for i in range(2, n+1):\n            for j in range(1, 7):\n                for k in range(1, rollMax[j-1]+1):\n                    if i-k < 0:\n                        break\n                    elif i-k == 0:\n                        dp[i][j] += 1\n                    else:\n                        dp[i][j] += sum([dp[i-k][l] for l in range(1, 7) if l != j])\n        return sum(dp[-1]) % (10**9+7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        kmax = 15\n        kmod = pow(10, 9) + 7\n        \n        # dp[i][j][k]: # of sequences ends with k consecutive j after i rolls\n        dp = [[[0] * (kmax + 1) for _ in range(6)] for _ in range(n + 1)]\n        \n        for j in range(6):\n            dp[1][j][1] = 1\n            \n        for i in range(2, n + 1):\n            for j in range(6):\n                for p in range(6):\n                    for k in range(1, rollMax[p] + 1):\n                        if p != j:\n                            dp[i][j][1] = (dp[i][j][1] + dp[i - 1][p][k]) % kmod\n                        elif k < rollMax[p]:\n                            dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i - 1][p][k]) % kmod\n                            \n        ans = 0\n        for j in range(6):\n            for k in range(1, rollMax[j] + 1):\n                ans = (ans + dp[n][j][k]) % kmod\n                \n        return ans\n", "from functools import lru_cache\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        @lru_cache(None)\n        def dfs(rolls_left, prev_roll, num_repeats):\n            if rolls_left == 0:\n                return 1\n            ans = 0\n            for roll in range(6):\n                if roll == prev_roll:\n                    if rollMax[roll] - num_repeats > 0:\n                        ans += dfs(rolls_left-1, prev_roll, num_repeats+1)\n                else:\n                    ans += dfs(rolls_left-1, roll, 1)\n            return ans % (10**9 + 7)\n        \n        return dfs(n, -1, 0)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        M = pow(10, 9) + 7\n        rollMax = [0] + rollMax\n        dp = [[[0] * (15 + 1) for _ in range(6 + 1)] for _ in range(n + 1)]\n        \n        # \u629b\u7b2c\u4e00\u6b21\u9ab0\u5b50\uff0c\u51fa\u73b0\u6570\u5b57 i \u7684\u6b21\u6570\n        for i in range(1, 6 + 1):\n            dp[1][i][1] = 1\n        \n        for i in range(2, n + 1): # \u7b2c i \u6b21\u629b\n            for j in range(1, 6 + 1): # \u5f97\u5230\u9ab0\u5b50\u7684num\u6570\n                for k in range(1, rollMax[j] + 1): # \u8fd9\u4e2a\u6570\u5b57\u7b2c k\u6b21\u51fa\u73b0\n                    if k > 1:\n                        dp[i][j][k] = dp[i-1][j][k-1]\n                    else:\n                        for jj in range(1, 6 + 1):\n                            for kk in range(1, rollMax[jj] + 1):\n                                if jj != j:\n                                    dp[i][j][k] += dp[i-1][jj][kk]\n        \n        res = 0\n        for i in range(1, 7):\n            for j in range(1, rollMax[i] + 1):\n                res += dp[n][i][j]\n        return res % M", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        dp =collections.deque([[1] * 7 for i in range(max(rollMax) + 1)])\n        dp[-1][-1] = 6\n        for i in range(2,  n + 1):\n            dp2 = [0] * 7\n            for j in range(6):\n                if i - rollMax[j] <= 0:\n                    dp2[j] = dp[-1][-1]\n                elif i - rollMax[j] == 1:\n                    dp2[j] = dp[-1][-1] - 1 \n                else:\n                    p = dp[-rollMax[j] - 1]\n                    dp2[j] = (dp[-1][-1] - p[-1] + p[j]) % MOD\n                dp2[-1] = (dp2[-1] + dp2[j]) % MOD\n            dp.popleft()\n            dp.append(dp2)\n        return dp[-1][-1]\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]\n        for j in range(len(rollMax)):\n            dp[1][j] = 1\n        \n        dp[1][-1] = 6\n        \n        for i in range(2, n + 1):\n            for j in range(len(rollMax)):\n                dp[i][j] = dp[i - 1][-1]\n                k = i - rollMax[j]\n                if k == 1:\n                    dp[i][j] -= 1\n                elif k > 1:\n                    dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])\n                dp[i][-1] += dp[i][j]\n                \n        return dp[n][len(rollMax)] % (10**9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * (n+1) for _ in range(6)]\n        \n        for roll in range(1, n+1):\n            for face in range(6):\n                if roll == 1:\n                    dp[face][roll] = 1\n                else:\n                    for k in range(1, rollMax[face]+1):\n                        if roll - k < 0:\n                            break\n                        elif roll - k == 0:\n                            dp[face][roll] += 1\n                        else:\n                            for l in range(6):\n                                if l != face:\n                                    dp[face][roll] += dp[l][roll-k]\n        \n        res = 0 \n        for i in range(6):\n            res += dp[i][-1]\n        \n        return res % (10**9 + 7)", "#[] DP\n#O(6N * 6T): T: upperbound of rollMax\n\n#f(i, d): number of combinations of res[0~i] if the last number is d\n#f(i, ?) = 1 if i == 0\n#               d'd d d ... d [d]\n#               ? d'd d ... d [d]\n#               ? ? d'd ... d [d]\n#               ? ? ? d'... d [d]\n#               ? ? ? ? ... d'[d]\n#f(i, d) = sum{ f(j, d') for j in i-rollMax[d] ~ i-1 for d' in 0~5\n#               if i-rollMax[d] >= 0 and d' != d }\n#          sum{ f(i-1, d') for any d' if rollMax[d] < i} < no limit\nMOD = 1000000007\ndef memorized(f):\n    memo = {}\n    def helper(*arg):\n        if arg not in memo:\n            memo[arg] = f(*arg)\n        return memo[arg]\n    return helper\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @memorized\n        def f(i: int, d: int):\n            if i == 0:\n                return 1\n            if i >= rollMax[d]:\n                return sum(f(j, d2) for j in range(i-rollMax[d], i) for d2 in range(6) if d2 != d) % MOD\n            else:\n                return sum(f(i-1, d2) for d2 in range(6)) % MOD\n        return sum(f(n-1, d) for d in range(6)) % MOD", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dp[i][j][k] means this is ith roll and we end up with number j and it has lasted k times\n        dp = [[[0 for k in range(16)] for j in range(7)] for i in range(n + 1)]\n        mod = pow(10, 9) + 7\n        \n        for j in range(1, 7):\n            dp[1][j][1] = 1\n        \n        for i in range(2, n + 1):\n            for j in range(1, 7):\n                for prev in range(1, 7):\n                    for k in range(1, rollMax[prev - 1] + 1):\n                        if j != prev:\n                            dp[i][j][1] = (dp[i][j][1] + dp[i - 1][prev][k]) % mod\n                        else:\n                            if k < rollMax[prev - 1]:\n                                dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i - 1][j][k])\n        \n        ans = 0\n        for j in range(1, 7):\n            for k in range(1, rollMax[j - 1] + 1):\n                ans = (ans + dp[n][j][k]) % mod\n        \n        return ans", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        @lru_cache(None)\n        def roll(i, j, k):\n            if i == 0:\n                return 1\n            cnt = 0 \n            for d in range(6):\n                if d == j:\n                    if k < rollMax[j]:\n                        cnt = (cnt + roll(i - 1, d, k + 1)) % MOD\n                else:\n                    cnt = (cnt + roll(i - 1, d, 1)) % MOD\n            return cnt\n        \n        return roll(n, -1, 0)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[[0 for k in range(16)] for j in range(6)] for i in range(n)]\n        \n        for s in range(6):\n            dp[0][s][1] = 1\n            \n        for i in range(1,n):\n            for j in range(6):\n                for k in range(1,rollMax[j]+1):\n                    if k > 1:\n                        dp[i][j][k] = dp[i-1][j][k-1]\n                    else:\n                        for jj in range(6):\n                            for kk in range(1,rollMax[jj]+1):\n                                if j == jj:\n                                    continue\n                                dp[i][j][k] += dp[i-1][jj][kk]\n        ans = 0\n        for l in range(6):\n            for m in range(1,rollMax[l]+1):\n                ans += dp[n-1][l][m]\n        \n        return ans%(10**9+7)\n                    \n                        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0]*(len(rollMax)+1) for _ in range(n+1)]\n        \n        for idx in range(len(rollMax)):\n            dp[1][idx] = 1\n            dp[1][-1] += dp[1][idx]\n        \n        for row in range(2, n+1):\n            for col in range(len(rollMax)):\n                dp[row][col] = dp[row-1][-1]\n                \n                delta = row-rollMax[col]\n                \n                if delta == 1:\n                    dp[row][col] -= 1\n                elif delta > 1:\n                    dp[row][col] -= (dp[delta-1][-1] - dp[delta-1][col])\n                \n                dp[row][-1] += dp[row][col]\n        \n        return dp[n][len(rollMax)] % (pow(10,9)+7)", "class Solution:\n    #dp[i][j][k] c!=k dp[i-1][j-1][c]\n    #dp[i][j][k]\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        #from inner to outer \n        dp=[[[0 for k in range(16)] for j in range(6)] for i in range(n)]\n        #print(len(dp),len(dp[0]),len(dp[0][0]))\n        mod=1e9+7\n        for i in range(6):\n            dp[0][i][1]=1\n        #print(dp)\n        for i in range(1,n):\n            for j in range(6):\n                for k in range(1,16):\n                    if k==1:\n                        for jj in range(6):\n                            for kk in range(1,rollMax[jj]+1):\n                                if j!=jj:\n                                    # print(kk,jj,i,j,k)\n                                    try:\n                                        dp[i][j][k]=(dp[i][j][k]+dp[i-1][jj][kk])%mod\n                                    except IndexError as e:\n                                        print((kk,jj,i,j,k))\n                    else:\n                        dp[i][j][k]=dp[i-1][j][k-1]\n        res=0\n        for j in range(6):\n            for k in range(1, rollMax[j]+1):\n                res=(res+dp[n-1][j][k])%mod\n        return int(res)\n                                \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dynamic programming\n        # dp[i][j][k] # at pos i, we end with j, and the number of continuous of j at the end is k\n\n        dp = [ [ [ 0 for k in range(rollMax[j] + 1)] for j in range(6)] for _ in range(n)]\n        \n        for j in range(6):\n            dp[0][j][1] = 1\n        \n        for i in range(n):\n            for j in range(6):\n                for k in range(2, rollMax[j] + 1):\n                    dp[i][j][k] += dp[i - 1][j][k - 1]\n                \n                for otherj in range(6):\n                    if otherj != j:\n                        for k in range(1, rollMax[otherj] + 1):\n                            dp[i][j][1] += dp[i - 1][otherj][k]\n        # print(\\\"dp=\\\", dp)\n        return sum([sum(x)%(10**9 + 7) for x in dp[-1]])%(10**9 + 7)\n# \u9898\u89e3\uff0c\u8fd9\u79cd\u8ba1\u7b97\u4e2a\u6570\u7684\u4e00\u822c\u90fd\u662f\u52a8\u6001\u89c4\u5212\u3002\u6ce8\u610f\u5230\u9898\u76ee\u4e2d rollMax[i] >=1\u8bf4\u660e \u53ea\u8981\u4e0a\u4e00\u4e2a\u4e0d\u4e00\u6837\uff0c\u90a3\u4e48\u6211\u8fd9\u6b21\u51fa\u90a3\u4e2a\u6570\u5b57\u90fd\u662f\u53ef\u4ee5\u7684\u3002\u6700\u540e\u522b\u5fd8\u4e86\u6c42 mod\n# \u52a8\u6001\u89c4\u5212\uff0c \u6700\u91cd\u8981\u7684\u662f\uff0c\u8981\u8bb0\u5f55\u54ea\u79cd\u72b6\u6001\u3002\u8fd9\u91cc \u8981\u6c42\u7684\u662f \u67d0\u4e2a number \u4e0d\u80fd\u8fde\u7eed\u8d85\u8fc7 rollMax[j]\u6b21\uff0c\u90a3\u4e48\u663e\u7136\u6211\u4eec\u9700\u8981\u8bb0\u5f55\u8fd9\u4ef6\u4e8b\u3002\u7136\u540e\u5f53\u524d\u7684\u4f4d\u7f6e\u9700\u8981\u8bb0\u5f55\uff0c\u6700\u540e\u4e00\u4e2a\u6570\u5b57\u662f\u4ec0\u4e48\u9700\u8981\u8bb0\u5f55\uff0c\u6700\u540e\u4e00\u4e2a\u6570\u5b57\u51fa\u73b0\u591a\u5c11\u6b21\uff0c\u9700\u8981\u8bb0\u5f55\uff0c\u4e8e\u662f\u4e09\u7ef4 dp \u51fa\u73b0\u4e86\u3002\n\n#dp[i][j][k] \u4ee3\u8868 \u5230\u7b2c i \u4e2a\u4f4d\u7f6e\u65f6\uff0c\u4ee5\u6570\u5b57 j \u7ed3\u5c3e\uff0c\u7ed3\u5c3e\u5904 \u8fde\u7eed\u51fa\u73b0 k \u6b21\u3002 \u90a3\u4e48\u5176\u5b9e\u8fd9\u91cc\u5c31\u8981\u6c42 k >= 1 \u7684\uff0c\u56e0\u4e3a\u4ee5 j\u7ed3\u5c3e\u4e86\uff0c\u90a3\u4e48\u80af\u5b9a\u81f3\u5c11\u6709\u4e00\u4e2a\u6570\u5b57\u4e86\u3002\n# dp \u4e09\u7ef4\u6570\u7ec4\u7684\u7ef4\u5ea6\u600e\u4e48\u786e\u5b9a\u5462\uff1f i\uff0cj \u662f\u5f88\u663e\u7136\uff0c\u4e00\u4e2a\u662f n\uff0c\u4e00\u4e2a\u662f6\uff0c\u90a3\u4e48k\u7ef4\u5ea6\uff0c\u6211\u4eec\u7528 roolMax[j] + 1 \u8fd9\u4e2a\u7ef4\u5ea6\uff0c\u56e0\u4e3a \u6211\u4eec\u51fa\u73b0\u7684\u4e2a\u6570 0\uff0c1\uff0c2\uff0c3\uff0c4\uff0c\u3002\u3002\u3002\uff0c\u4e00\u76f4\u5230 roolMax[j] \u90fd\u662f\u53ef\u4ee5\u7684\uff0c\u6240\u4ee5 range \uff08roolMax[j] + 1).\n# \u90a3\u4e48 j \u7528 range(6) = 0, 1, 2, 3, 4,5 \u8fd9\u91cc\u662f\u6ca1\u6709\u5173\u7cfb\u7684\uff0c\u6b63\u597d\u548c roolMax[j] \u7684 index \u5bf9\u5e94\u8d77\u6765\u3002 \u4e0d\u7528 \u6362\u6210 1\uff0c2\uff0c3\uff0c4\uff0c5\uff0c6.\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dynamic programming\n        # dp[i][j][k] # at pos i, we end with j, and the number of continuous of j at the end is k\n\n        dp = [ [ [ 0 for k in range(rollMax[j] + 1)] for j in range(6)] for _ in range(n)]\n        \n        for j in range(6):\n            dp[0][j][1] = 1\n        \n        for i in range(n):\n            for j in range(6):\n                for k in range(2, rollMax[j] + 1): # \u8fd9\u91cc \u539f\u5219\u4e0a\u6765\u8bf4\u5e94\u8be5\u5199\u6210 range(2)\u5f00\u59cb\uff0c\u56e0\u4e3a k-1>=1,\u4f46\u662f\u5199\u6210 1\u4e5f\u6ca1\u6709\u5173\u7cfb\uff0c\u56e0\u4e3a k-1=0, += 0, \u6ca1\u6709\u5f71\u54cd\u3002\n                    dp[i][j][k] += dp[i - 1][j][k - 1]\n                \n                for otherj in range(6):\n                    if otherj != j:\n                        for k in range(1, rollMax[otherj] + 1):\n                            dp[i][j][1] += dp[i - 1][otherj][k]\n        # print(\\\"dp=\\\", dp)\n        return sum([sum(x)%(10**9 + 7) for x in dp[-1]])%(10**9 + 7)\n# \u9898\u89e3\uff0c\u8fd9\u79cd\u8ba1\u7b97\u4e2a\u6570\u7684\u4e00\u822c\u90fd\u662f\u52a8\u6001\u89c4\u5212\u3002\u6ce8\u610f\u5230\u9898\u76ee\u4e2d rollMax[i] >=1\u8bf4\u660e \u53ea\u8981\u4e0a\u4e00\u4e2a\u4e0d\u4e00\u6837\uff0c\u90a3\u4e48\u6211\u8fd9\u6b21\u51fa\u90a3\u4e2a\u6570\u5b57\u90fd\u662f\u53ef\u4ee5\u7684\u3002\u6700\u540e\u522b\u5fd8\u4e86\u6c42 mod\n# \u52a8\u6001\u89c4\u5212\uff0c \u6700\u91cd\u8981\u7684\u662f\uff0c\u8981\u8bb0\u5f55\u54ea\u79cd\u72b6\u6001\u3002\u8fd9\u91cc \u8981\u6c42\u7684\u662f \u67d0\u4e2a number \u4e0d\u80fd\u8fde\u7eed\u8d85\u8fc7 rollMax[j]\u6b21\uff0c\u90a3\u4e48\u663e\u7136\u6211\u4eec\u9700\u8981\u8bb0\u5f55\u8fd9\u4ef6\u4e8b\u3002\u7136\u540e\u5f53\u524d\u7684\u4f4d\u7f6e\u9700\u8981\u8bb0\u5f55\uff0c\u6700\u540e\u4e00\u4e2a\u6570\u5b57\u662f\u4ec0\u4e48\u9700\u8981\u8bb0\u5f55\uff0c\u6700\u540e\u4e00\u4e2a\u6570\u5b57\u51fa\u73b0\u591a\u5c11\u6b21\uff0c\u9700\u8981\u8bb0\u5f55\uff0c\u4e8e\u662f\u4e09\u7ef4 dp \u51fa\u73b0\u4e86\u3002\n\n#dp[i][j][k] \u4ee3\u8868 \u5230\u7b2c i \u4e2a\u4f4d\u7f6e\u65f6\uff0c\u4ee5\u6570\u5b57 j \u7ed3\u5c3e\uff0c\u7ed3\u5c3e\u5904 \u8fde\u7eed\u51fa\u73b0 k \u6b21\u3002 \u90a3\u4e48\u5176\u5b9e\u8fd9\u91cc\u5c31\u8981\u6c42 k >= 1 \u7684\uff0c\u56e0\u4e3a\u4ee5 j\u7ed3\u5c3e\u4e86\uff0c\u90a3\u4e48\u80af\u5b9a\u81f3\u5c11\u6709\u4e00\u4e2a\u6570\u5b57\u4e86\u3002\n# dp \u4e09\u7ef4\u6570\u7ec4\u7684\u7ef4\u5ea6\u600e\u4e48\u786e\u5b9a\u5462\uff1f i\uff0cj \u662f\u5f88\u663e\u7136\uff0c\u4e00\u4e2a\u662f n\uff0c\u4e00\u4e2a\u662f6\uff0c\u90a3\u4e48k\u7ef4\u5ea6\uff0c\u6211\u4eec\u7528 roolMax[j] + 1 \u8fd9\u4e2a\u7ef4\u5ea6\uff0c\u56e0\u4e3a \u6211\u4eec\u51fa\u73b0\u7684\u4e2a\u6570 0\uff0c1\uff0c2\uff0c3\uff0c4\uff0c\u3002\u3002\u3002\uff0c\u4e00\u76f4\u5230 roolMax[j] \u90fd\u662f\u53ef\u4ee5\u7684\uff0c\u6240\u4ee5 range \uff08roolMax[j] + 1).\n# \u90a3\u4e48 j \u7528 range(6) = 0, 1, 2, 3, 4,5 \u8fd9\u91cc\u662f\u6ca1\u6709\u5173\u7cfb\u7684\uff0c\u6b63\u597d\u548c roolMax[j] \u7684 index \u5bf9\u5e94\u8d77\u6765\u3002 \u4e0d\u7528 \u6362\u6210 1\uff0c2\uff0c3\uff0c4\uff0c5\uff0c6.\n", "import collections as clc\nimport functools as ft\n\n\nclass Solution:\n    \n    BASE = 10 ** 9 + 7\n    \n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        state = clc.defaultdict(int)\n        state[1, 0] = 1\n        for _ in range(n):\n            new_state = clc.defaultdict(int)\n            for (last_roll, streak), count in list(state.items()):\n                for dice in range(1, 7):\n                    if dice == last_roll:\n                        if streak >= rollMax[last_roll - 1]:\n                            continue\n                        new_state[dice, streak + 1] = (new_state[dice, streak + 1] + count) % self.BASE\n                    else:\n                        new_state[dice, 1] = (new_state[dice, 1] + count) % self.BASE\n            state = new_state\n        return sum(state.values()) % self.BASE\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dynamic programming\n        # dp[i][j][k] # at pos i, we end with j, and the number of continuous of j at the end is k\n        \n        dp = [ [ [ 0 for k in range(rollMax[j] + 1)] for j in range(6)] for _ in range(n)]\n        \n        for j in range(6):\n            dp[0][j][1] = 1\n        \n        for i in range(n):\n            for j in range(6):\n                for k in range(1, rollMax[j] + 1):\n                    dp[i][j][k] += dp[i - 1][j][k - 1]\n                \n                for otherj in range(6):\n                    if otherj != j:\n                        for k in range(1, rollMax[otherj] + 1):\n                            dp[i][j][1] += dp[i - 1][otherj][k]\n        # print(\\\"dp=\\\", dp)\n        return sum([sum(x)%(10**9 + 7) for x in dp[-1]])%(10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        states = {(None, 1): 1}\n        \n        for _ in range(n):\n            new_states = collections.defaultdict(int)\n            for state, count in list(states.items()):\n                for i in range(1, 7):\n                    if i == state[0]:\n                        if state[1] + 1 <= rollMax[i - 1]:\n                            new_states[(i, state[1] + 1)] += count\n                    else:\n                        new_states[(i, 1)] += count\n            states = new_states\n        return sum(states.values()) % (10 ** 9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        maxRolls = min(n, max(rollMax))\n        dp = [[[0] * (maxRolls + 1) for _ in range(7)] for _ in range(n + 1)]\n        \n        # Base case\n        for j in range(1, 7):\n            dp[1][j][1] = 1\n        \n        for i in range(2, n + 1):\n            for j in range(1, 7):\n                for k in range(1, min(i, rollMax[j - 1]) + 1):\n                    if k > 1:\n                        # Last roll was also a j\n                        dp[i][j][k] = sumMod(dp[i][j][k], dp[i - 1][j][k - 1])\n                        continue\n                    \n                    # Last roll was a jj != j\n                    for jj in range(1, 7):\n                        if jj == j:\n                            continue\n\n                        for kk in range(1, min(i - 1, rollMax[jj - 1]) + 1):\n                            dp[i][j][k] = sumMod(dp[i][j][k], dp[i - 1][jj][kk])\n        \n        result = 0\n        for j in range(1, 7):\n            for k in range(1, min(n, rollMax[j - 1]) + 1):\n                result = sumMod(result, dp[n][j][k])\n        \n        return result\n    \n    \ndef sumMod(x: int, y: int) -> int:\n    return (x + y) % (10 ** 9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * 7 for _ in range(n)]\n        for j in range(6):\n            dp[0][j] = 1\n        dp[0][-1] = 6\n        \n        for i in range(1, n):\n            total = 0\n            for j in range(6):\n                dp[i][j] = dp[i - 1][-1]\n                if i - rollMax[j] == 0:\n                    dp[i][j] -= 1\n                if i - rollMax[j] >= 1:\n                    dp[i][j] -= dp[i - rollMax[j] - 1][-1] - dp[i - rollMax[j] - 1][j]\n                total += dp[i][j]\n            dp[i][-1] = total\n            \n        return dp[-1][-1] % (10 ** 9 + 7)\n                    \n", "from functools import lru_cache\nclass Solution:    \n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10 ** 9 + 7\n\n        @lru_cache(None)\n        def dfs(n, last_idx, curr_len):\n            if n == 0:\n                return 1\n            \n            cnt = 0     \n            for i in range(6):\n                if i != last_idx or curr_len < rollMax[i]:\n                    temp = 1 if i != last_idx else curr_len + 1\n                    cnt += dfs(n-1, i, temp)\n            return cnt % mod\n        return dfs(n, -1, 0)\n                    \n                    \n            \n", "import functools\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        max_remaining = sum(rollMax)\n\n        @functools.lru_cache(None)\n        def count_sequences(last_index, last_remaining, rolls_left):\n            if last_remaining < 0:\n                return 0\n            if rolls_left == 0:\n                return 1\n\n            sequences_from_here = 0\n            for i in range(len(rollMax)):\n                if i == last_index:\n                    sequences_from_here += count_sequences(i, last_remaining - 1, rolls_left - 1)\n                else:\n                    sequences_from_here += count_sequences(i, rollMax[i] - 1, rolls_left - 1)\n            return sequences_from_here % (10 ** 9 + 7)\n\n        return sum(count_sequences(i, rollMax[i] - 1, n - 1) for i in range(len(rollMax))) % (10 ** 9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = {(i, 1):1 for i in range(6)}\n        mod = 10**9+7\n        for _ in range(1, n):\n            dp2 = {}\n            for r, t in dp:\n                for i in range(6):\n                    if r==i:\n                        if t==rollMax[i]:\n                            continue\n                        else:\n                            dp2[(r, t+1)] = dp[(r, t)]%mod\n                    else:\n                        dp2[(i, 1)] = (dp2.get((i, 1), 0)+dp[(r, t)])%mod\n            \n            dp = dp2\n        \n        return sum(dp.values())%mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        self.total = 0\n        \n        @lru_cache(maxsize = 1000) \n        def digit(last,lastcount,k):\n            if k == n:\n                return 1\n                            \n            curnum= 0\n            \n            for i in range(6):\n                if i == last and k != 0:\n                    curcount = lastcount + 1\n                else:\n                    curcount = 1\n                    \n                if rollMax[i] < curcount:\n                    continue\n                else:            \n                    curnum += digit(i,curcount,k+1)\n            return curnum%(10**9+7)\n        \n        return digit(0,0,0)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        from functools import lru_cache\n        @lru_cache(maxsize = None)\n        def bt(dieLeft, lastVal, lastConsecCount):\n            if dieLeft == 0:\n                return 1\n            \n            total = 0\n            for i in range(0, 6):\n                if i == lastVal and lastConsecCount == rollMax[i]:\n                    continue\n                else:\n                    if i == lastVal:\n                        newCount = lastConsecCount + 1\n                        #print(lastVal, lastConsecCount)\n                    else:\n                        newCount = 1\n                    \n                    total += bt(dieLeft - 1, i, newCount)\n                    if total > 10**9 + 7:\n                        total = total % (10**9 + 7)\n            return total\n        \n        return bt(n, None, None)\n        \n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        from collections import defaultdict\n        LARGE = int(1e9+7)\n        \n        die_prev_to_combination = {(i,1):1 for i in range(1,7)}\n        for i in range(n-1):\n            next_die_prev_to_combination = defaultdict(int)\n            for die_and_prev, combination in list(die_prev_to_combination.items()):\n                die, prev = die_and_prev\n                for next_die in range(1,7):\n                    if next_die==die:\n                        if prev==rollMax[die-1]:\n                            continue\n                        else:\n                            next_die_prev_to_combination[(next_die, prev+1)] += combination\n                    else:\n                        next_die_prev_to_combination[(next_die,1)] += combination\n            die_prev_to_combination = next_die_prev_to_combination\n            \n        return sum(c for d,c in list(die_prev_to_combination.items()))%LARGE\n", "from functools import lru_cache\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n\n        @lru_cache(None)\n        def dfs(residual, last, lastFre):\n            if residual == 0:\n                return 1\n            tmp = 0\n            if rollMax[last - 1] == lastFre:\n                for i in range(6):\n                    if i + 1 == last:\n                        continue\n                    tmp += dfs(residual - 1, i + 1, 1) % (10**9 + 7)\n            else:\n                for i in range(6):\n                    if i + 1 == last:\n                        tmp += dfs(residual - 1, last, lastFre + 1)% (10**9 + 7)\n                    else:\n                        tmp += dfs(residual - 1, i + 1, 1)% (10**9 + 7)\n            return tmp % (10**9 + 7)\n        \n        ans = 0\n        for j in range(1, 7):\n            ans += dfs(n-1, j, 1)\n            ans %=  (10**9 + 7)\n        return ans \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        memo = {}\n        def helper(n, lastnum):\n            if n == 0:\n                return 1\n            if (n, lastnum) in memo:\n                return memo[(n, lastnum)]\n            \n            res = 0\n            for num in range(6):\n                if num == lastnum: continue\n                for i in range(1, rollMax[num]+1):\n                    nxtn = n-i\n                    if nxtn < 0: break\n                    res += helper(nxtn, num)\n            memo[(n, lastnum)] = res%(10**9 + 7)\n            return memo[(n, lastnum)]\n        \n        return helper(n, None)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 1000000007\n        if (n == 0): return 0\n        dp = [[[0]*(max(rollMax)+2) for _ in range(7)] for __ in range(n+1)]\n        for i in range(1,7):\n            if (rollMax[i-1] > 0):\n                dp[1][i][1] = 1\n        for x in range(2,n+1):\n            for i in range(1,7):\n                for k in range(1, rollMax[i-1]):\n                    dp[x][i][k+1] = (dp[x-1][i][k])%MOD\n                for j in range(1,7):\n                    if (j == i): continue\n                    for k in range(1,rollMax[i-1]+1):\n                        dp[x][j][1] = (dp[x][j][1]+dp[x-1][i][k])%MOD\n        num = 0\n        for i in range(1,7):\n            for k in range(1,max(rollMax)+1):\n                num = (num + dp[n][i][k]) % MOD\n        return num\n            \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n\n#         dp = [[0] * 7 for _ in range(n)]\n#         dp[0] = [1] * 6 + [6]\n        \n#         for j in range(1, n):\n#             for i in range(6):\n                \n#                 dp[j][i] = dp[j - 1][-1]\n#                 k = j - rollMax[i]\n                \n#                 if k == 0:\n#                     dp[j][i] -= 1\n                \n#                 elif k > 0:\n#                     dp[j][i] -= (dp[k - 1][-1] - dp[k - 1][i])\n                    \n#                 # dp[i][-1] += dp[i][j]\n#             dp[i][6] = sum(dp[i][:6])\n                \n#         print (dp)\n                \n#         return dp[n-1][len(rollMax)] % int(1e9 + 7)\n        \n\n        dp = [[0] * 7 for _ in range(n)]\n        dp[0] = [1] * 6 + [6]\n\n        for r in range(1, n):\n            for c in range(6):\n                \n                dp[r][c] = dp[r-1][-1]\n                \n                k = r - rollMax[c]\n\n                if k == 0: # when all numbers = i\n                    dp[r][c] -= 1\n                    \n                elif k >= 1: # when we have prefix\n                    dp[r][c] -= (dp[k-1][-1] - dp[k-1][c])\n                \n            dp[r][6] = sum(dp[r][:6])\n            \n        # print (dp)\n            \n        return dp[-1][-1] % int(1e9 + 7)\n                    \n", "from collections import defaultdict\n\nclass Solution:\n  def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n    # O(15 x 6 x N)\n    M = 10 ** 9 + 7\n    # at i-th roll, count (last-roll, num consecutive rolls of same with last roll): num of combinations\n    q = {(-1, 0): 1}\n    for _ in range(n):\n      p = defaultdict(lambda: 0)\n      for x, r in q:\n        for y in range(6):\n          if y == x:\n            if r + 1 <= rollMax[y]:\n              p[(y, r + 1)] += q[(x, r)] % M\n          else:\n            p[(y, 1)] += q[(x, r)] % M\n      q = p\n    return sum(q.values()) % M\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = (10 ** 9) + 7\n        @lru_cache(maxsize=None)\n        def solve(n, last, last_count):\n            if n == 0:\n                return 1\n            ans = 0\n            for i in range(6):\n                if i == last and last_count > 0:\n                    ans += solve(n - 1, last, last_count - 1)\n                elif i != last and rollMax[i] > 0:\n                    ans += solve(n - 1, i, rollMax[i] - 1)\n            return ans % MOD\n        \n        return solve(n, -1, -1)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        maxRolls = min(n, max(rollMax))\n        dp = [[[0] * (maxRolls + 1) for _ in range(7)] for _ in range(2)]\n        \n        # Base case\n        for j in range(1, 7):\n            dp[1][j][1] = 1\n        \n        for i in range(2, n + 1):\n            iMod2 = i % 2\n            iMinus1Mod2 = (i - 1) % 2\n            \n            for j in range(1, 7):\n                # Last roll was a jj != j\n                dp[iMod2][j][1] = 0\n                for jj in range(1, 7):\n                    if jj == j:\n                        continue\n                    for kk in range(1, min(i - 1, rollMax[jj - 1]) + 1):\n                        dp[iMod2][j][1] = sumMod(dp[iMod2][j][1], dp[iMinus1Mod2][jj][kk])\n                \n                # Last roll was also a j\n                for k in range(2, min(i, rollMax[j - 1]) + 1):\n                    dp[iMod2][j][k] = dp[iMinus1Mod2][j][k - 1]\n        \n        result = 0\n        nMod2 = n % 2\n        for j in range(1, 7):\n            for k in range(1, min(n, rollMax[j - 1]) + 1):\n                result = sumMod(result, dp[nMod2][j][k])\n        \n        return result\n    \n    \ndef sumMod(x: int, y: int) -> int:\n    return (x + y) % (10 ** 9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10**9 + 7\n        \n        dp = [[0, 1] + [0] * 15 for i in range(6)]\n        \n        for _ in range(n - 1):\n            dp2 = [[0] * 17 for i in range(6)]\n            for i in range(6):\n                for k in range(1, rollMax[i] + 1):\n                    for j in range(6):\n                        if i == j:\n                            if k < rollMax[i]:\n                                dp2[j][k + 1] += dp[i][k] % mod\n                        else:\n                            dp2[j][1] += dp[i][k] % mod\n            dp = dp2\n        \n        return sum(sum(row) for row in dp) % mod\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        self.total = 0\n        \n        @lru_cache(maxsize = 100000000)\n        #memo = [[[-1 for _ in range(n)] for _ in range(max(rollMax)+1)] for _ in range(6)]\n        def digit(last,lastcount,k):          \n            if k == n:\n                return 1    \n           # elif memo[last][lastcount][k] != -1:\n                #return memo[last][lastcount][k]\n            curnum= 0\n            \n            for i in range(6):\n                if i == last and k != 0:\n                    curcount = lastcount + 1\n                else:\n                    curcount = 1\n                    \n                if rollMax[i] < curcount:\n                    continue\n                else:            \n                    curnum += digit(i,curcount,k+1)\n            #memo[last][lastcount][k] = curnum%(10**9+7)\n            return curnum%(10**9+7)#memo[last][lastcount][k]\n        \n        return digit(0,0,0)\n", "\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.ans = 0\n        @lru_cache(maxsize=None)\n        def rec(index,k,num):\n            if index == n:\n                return 1\n            ans = 0 \n            for i in range(6):\n                if i!=k:\n                    ans += rec(index+1,i,1)\n                elif num+1 <= rollMax[i]:\n                    ans += rec(index+1,i,num+1)\n            return ans\n                \n       \n        \n            \n        return rec(0,-1,0)% ((10**9)+7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        self.total = 0\n        \n        @lru_cache(maxsize = 100000)\n        #memo = [[[-1 for _ in range(n)] for _ in range(max(rollMax)+1)] for _ in range(6)]\n        def digit(last,lastcount,k):          \n            if k == n:\n                return 1    \n           # elif memo[last][lastcount][k] != -1:\n                #return memo[last][lastcount][k]\n            curnum= 0\n            \n            for i in range(6):\n                if i == last and k != 0:\n                    curcount = lastcount + 1\n                else:\n                    curcount = 1\n                    \n                if rollMax[i] < curcount:\n                    continue\n                else:            \n                    curnum += digit(i,curcount,k+1)\n            #memo[last][lastcount][k] = curnum%(10**9+7)\n            return curnum%(10**9+7)#memo[last][lastcount][k]\n        \n        return digit(0,0,0)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @lru_cache(maxsize=None)\n        def dfs(n, i, k):\n            if not n: return 1\n            ans = 0\n            for j in range(6):\n                if i != j: ans += dfs(n-1, j, 1)\n                elif k+1 <= rollMax[j]: ans += dfs(n-1, j, k+1)\n            return ans    \n        return sum(dfs(n-1, i, 1) for i in range(6)) % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        memo = {}\n        def die_simulator_starting_at(start: int, n: int):\n            if (start, n) in memo:\n                return memo[start, n]\n            if n == 1:\n                memo[start, n] = 1\n            else:\n                count = 0\n                for j in range(1, min(n, rollMax[start] + 1)):\n                    for nxt in range(6):\n                        # hack to count a run of \\\"start\\\"s at the end\n                        if nxt != start or j == n - 1 and j < rollMax[start]:\n                            count = (count + die_simulator_starting_at(nxt, n - j)) % 1000000007\n                memo[start, n] = count\n            return memo[start, n]\n        return sum(die_simulator_starting_at(i, n) for i in range(6)) % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @lru_cache(maxsize=None)\n        def recursion(n,last,freq):\n            if n == 0 : \n                return 1\n            answer = 0\n            for i in range(6) :\n                if i == last :\n                    if freq == rollMax[i] : continue\n                    else :\n                        answer+=recursion(n-1,last,freq+1)\n                else :\n                    answer+=recursion(n-1,i,1)\n            return answer\n        return recursion(n,-1,0)%(10**9+7)", "from functools import lru_cache\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        @lru_cache(None)\n        def dfs(i, r, t):\n            if i == 0:\n                return 1\n            \n            s = 0\n            for k in range(6):\n                if r == k:\n                    if t < rollMax[k]:\n                        s += dfs(i-1, r, t+1)\n                else:\n                    s += dfs(i-1, k, 1)\n            return s\n        \n        return dfs(n, -1, 0) % (10 ** 9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dp[i][j][k] : ith roll, end with j with consecutive k times\n        MOD = 10 ** 9 + 7\n        rdim = max(rollMax)\n        dp = [[[0] * rdim for _ in range(6)] for _ in range(n)]\n        \n        # init\n        for j in range(6):\n            dp[0][j][0] = 1\n        \n        for i in range(1, n):\n            for j in range(6):\n                for prev in range(6):\n                    for k in range(rollMax[prev]):\n                        if j == prev and k < rollMax[prev] - 1:\n                            dp[i][j][k + 1] += dp[i - 1][prev][k] % MOD\n                        if j != prev:\n                            dp[i][j][0] += dp[i - 1][prev][k] % MOD\n        \n        return sum(dp[n - 1][j][k] for j in range(6) for k in range(rdim)) % MOD", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dp[i][j][k]: number of sequences end with k js when throw dice for i times\n        # dp[i][*][1] = 1\n        # dp[i][j][1] = sum(dp[i - 1][p][*]) j != p\n        # dp[i][j][k + 1] = dp[i - 1][j][k] k < rollMax[j]\n        mod = 10**9 + 7\n        maxRoll = max(rollMax)\n        dp = [[[0] * (maxRoll + 1) for _ in range(6)] for _ in range(n + 1)]\n        for j in range(6):\n            dp[1][j][1] = 1\n        for i in range(2, n + 1):\n            for j in range(6):\n                for p in range(6):\n                    for k in range(1, rollMax[p] + 1):\n                        if p != j:\n                            dp[i][j][1] = (dp[i][j][1] + dp[i - 1][p][k]) % mod\n                        elif k < rollMax[p]:\n                            dp[i][j][k + 1] = dp[i - 1][j][k]\n        res = 0\n        for j in range(6):\n            for k in range(1, rollMax[j] + 1):\n                res = (res + dp[n][j][k]) % mod\n        return res", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @lru_cache(None)\n        def fun(last,no,con):\n            if no == n:\n                return 1\n            count = 0\n            for i in range(6):\n                if i != last:\n                    count+=fun(i,no+1,1)\n                elif con < rollMax[i]:\n                    count += fun(i,no+1,con+1)\n            return count\n        ans = 0\n        for i in range(6):\n            ans+= fun(i,1,1)\n        return ans%(10**9+7)\n", "from functools import lru_cache \nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        #dp[idx,prev]  = (dp[idx-1,prev] +  \n        @lru_cache(None)\n        def helper(idx,prev):\n            e,c = prev \n            if idx == n:\n                return 1\n            count = 0 \n            for i in range(6):\n                if e == i:\n                    if c<rollMax[i]:\n                        count += helper(idx+1,(i,c+1))% (10**9 + 7)\n                else:\n                    count += helper(idx+1,(i,1)) % (10**9 + 7)\n            return count %  (10**9 + 7)\n        return helper(0,(-1,0)) % (10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        maxAns = 10**9 + 7\n        krollMax = 15\n        \n        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]\n        # [n+1][6][15+1]\n        \n        for i in range(6):\n            dp[1][i][1] = 1\n        \n        for i in range(2,n+1):\n            for j in range(6):#current dice num\n                for p in range(6): # previous dice num \n                    for k in range(1, krollMax+1):\n                        if k>rollMax[p]: continue\n                        if j != p: #different than previous dice\n                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns\n                        elif k<rollMax[j]:\n                                dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns\n        ans = 0\n        for i in range(6):\n            for j in range(15+1):\n                ans += dp[n][i][j]\n        return ans % maxAns\n                            \n                    \n        \n", "from functools import lru_cache\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        @lru_cache(None)\n        # die value, consecutive rolls it came up, num rolls left\n        def roll(val, cons, left):\n            if left == 0:\n                return 1\n            ans = 0\n            if cons < rollMax[val]:\n                ans += roll(val, cons+1, left-1)\n            for nval in range(6):\n                if nval != val:\n                    ans += roll(nval, 1, left-1)\n            return ans\n        \n        return roll(0,0,n) % (10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        maxAns = 10**9 + 7\n        krollMax = 15\n        \n        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]\n        # [n+1][6][15+1]\n        \n        for i in range(6):\n            dp[1][i][1] = 1\n        \n        for i in range(2,n+1):\n            for j in range(6):#current dice num\n                for p in range(6): # previous dice num \n                    for k in range(1, krollMax+1):\n                        if k>rollMax[p]: continue\n                        if j != p: #different than previous dice\n                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns\n                        elif k<rollMax[j]:\n                            dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns\n        ans = 0\n        for i in range(6):\n            for j in range(15+1):\n                ans += dp[n][i][j]\n        return ans % maxAns\n                            \n                    \n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0]*n for i in range(6)]\n        m = 10**9+7\n        for i in range(n):\n            sum_ = 0\n            for j in range(6):\n                sum_ += dp[j][i-1]%m\n            sum_ = sum_%m\n            for j in range(6):\n                if i==0:\n                    dp[j][i] = 1\n                else:\n                    if i+1<=rollMax[j]:\n                        dp[j][i] = sum_\n                    else:\n                        s_ = 0\n                        if i-rollMax[j]==0:\n                            dp[j][i] = sum_ - 1\n                        else:\n                            for k in range(6):\n\n                                if k!=j:\n                                    s_ += dp[k][i-1-rollMax[j]]%m\n                            s_ = s_%m\n\n                            dp[j][i] =  sum_ - s_\n        res = 0\n        for i in range(6):\n            res += dp[i][-1]%m\n        #print(dp)\n        return res%m", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        @lru_cache(None)\n        def dfs(n, prev, consecutive):\n            if n == 0:\n                return 1\n            \n            res = 0\n            \n            for next_num in range(1, 7):\n                if next_num == prev:\n                    if consecutive < rollMax[next_num - 1]:\n                        res += dfs(n - 1, prev, consecutive + 1)\n                else:\n                    res += dfs(n - 1, next_num, 1)\n            \n            return res\n        \n        return dfs(n, None, 0) % MOD", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10 ** 9 + 7\n\n        @lru_cache(None)\n        def dfs(i, num, k):\n            if i == n:\n                return 1\n            ans = 0\n            for j in range(6):\n                if j != num:\n                    ans += dfs(i + 1, j, 1)\n                elif k < rollMax[j]:\n                    ans += dfs(i + 1, j, k + 1)\n            return ans\n\n        ans = 0\n        for i in range(6):\n            ans += dfs(1, i, 1)\n        return ans % mod\n                    \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        M, K = 6, 15\n        dp = [[[0]*(K + 1) for _ in range(M + 1)] for _ in range(n + 1)]\n        \n        for i in range(1, M+1):\n            dp[1][i][1] = 1\n            \n        for i in range(2, n+1):           \n            for j in range(1, M+1):  \n                \n                for m in range(1, M+1):\n                    if m != j:\n                        dp[i][j][1] += sum(dp[i-1][m][h] for h in range(1, rollMax[m-1] + 1))\n\n                for k in range(1, K):\n                    # print()\n                    # print(i, j, k)\n                    # print(i-j, j, k-1)\n                    dp[i][j][k+1] += dp[i-1][j][k]\n        \n        \n        # for i in range(1, n+1):\n            # for j in range(1, 7):\n                # print()\n                # print(\\\"i, j: \\\", i, j)\n                # print(\\\"dp[i][j]: \\\", dp[i][j])\n                \n        ans = 0\n        for m in range(1, M+1):\n            for k in range(1, rollMax[m-1] + 1):\n                ans += dp[-1][m][k]\n                \n        return ans % (10**9 + 7)", "class Solution:\n  def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n    # Basic solution: 3 dimensions, n rolls, last roll, last consecutive count -> O(n^2)\n    # Can we reduce to O(n) or O(nlogn)? Seems not.\n    d = {}\n    def dp(n, v, k): # n rolls, last is v, v has at most k consecutive (k > 1. Notice: don't handle k == 0, since it will include others repeated, e.g. k == 0 for 1 includes k == 0 for 2, etc.)\n#       if n == 1:\n#         return 1 if k == 1 else 0\n#       if (n, v, k) not in d:\n#         if k == 1:\n#           d[(n, v, k)] = 0\n#           for i, lim in enumerate(rollMax):\n#             if i != v:\n#               d[(n, v, k)]\n#         else:\n#           d[(n, v, k)] = dp(n-1, v, k-1)\n      \n      if n == 1:\n        return 1\n      if (n, v, k) not in d:\n        if k == 1:\n          d[(n, v, k)] = 0\n          for i, lim in enumerate(rollMax):\n            if i != v:\n              d[(n, v, k)] += dp(n-1, i, lim) # All others\n        elif k == 2:\n          d[(n, v, k)] = dp(n, v, 1) + dp(n-1, v, k-1)\n        else:\n          # atmost(n, v, k) = atmost(n, v, k-1) + exactly(n, v, k) = atmost(n, v, k-1) + exactly(n-1, v, k-1) = atmost(n, v, k-1) + atmost(n-1, v, k-1) - atmost(n-1, v, k-2)\n          d[(n, v, k)] = dp(n, v, k-1) + dp(n-1, v, k-1) - dp(n-1, v, k-2)\n      return d[(n, v, k)]\n    \n    def get_exact(n, v, k):\n      if k == 1:\n        return dp(n, v, k)\n      return dp(n, v, k) - dp(n, v, k-1)\n    \n    res = 0\n    for i, lim in enumerate(rollMax):\n      for j in range(1, lim+1):\n        res += get_exact(n, i, j)\n\n    return res % (10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @lru_cache(maxsize=None)\n        def dfs(n, i, k):\n            if not n: return 1\n            ans = 0\n            for j in range(6):\n                if i != j: ans += dfs(n-1, j, 1)\n                elif k+1 <= rollMax[j]: ans += dfs(n-1, j, k+1)\n            return ans    \n        return sum(dfs(n-1, i, 1) for i in range(6)) % 1000000007\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        #dp[i][j][k]: ith turn end with j continues number of k\n        dp = [ [[0]*6 for _ in range(16)] for _ in range(n) ]\n        \n        #iterate the first rolling\n        for k in range(6):\n            dp[0][1][k] = 1\n        \n        mod = 10**9+7\n        # iterate rest n-1 time rollings\n        for i in range(1,n):\n            # for this turn rolling ending with k\n            for k in range(6):\n                #for last turn rolling ending with prev\n                for prev in range(6):\n                    # for last turn ending with continous j number of prev \n                    for j in range(1,min(rollMax[prev],i+1)+1):\n                        if prev == k:\n                            dp[i][j][k]+=dp[i-1][j-1][k]\n                            dp[i][j][k]%=mod\n                        else:\n                            dp[i][1][k]+=dp[i-1][j][prev]\n                            dp[i][1][k]%=mod\n        \n        return sum(dp[n-1][j][k] for k in range(6) for j in range(1,min(n,rollMax[k])+1))%mod\n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        maxAns = 10**9 + 7\n        krollMax = 15\n        \n        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]\n        # [n+1][6][15+1]\n        \n        for i in range(6):\n            dp[1][i][1] = 1\n        \n        for i in range(2,n+1):\n            for j in range(6):#current dice num\n                for p in range(6): # previous dice num \n                    for k in range(1, krollMax+1):\n                        if k>rollMax[p]: continue\n                        if j != p: #different than previous dice\n                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns\n                        elif k<rollMax[j]:\n                            dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns\n        ans = 0\n        for i in range(6):\n            for j in range(rollMax[i]+1):\n                ans += dp[n][i][j]\n        return ans % maxAns\n                            \n                    \n        \n", "import functools\nclass Solution:\n    def dieSimulator(self, n: int, R: List[int]) -> int:\n        @functools.lru_cache(None)\n        def g(n,k):\n            if n < 1: return 0\n            if n == 1: return 1\n            return f(n-1) - f(n-R[k-1]-1) + g(n-R[k-1]-1,k)\n\n        @functools.lru_cache(None)\n        def f(n):\n            if n < 0 : return 0\n            if n == 0 : return 1\n            return sum([g(n,k) for k in range(1,7)])\n\n        return f(n) % (10 ** 9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        #dp[i][j][k]: ith turn end with j continues number of k\n        dp = [ [[0]*6 for _ in range(16)] for _ in range(n) ]\n        \n        #iterate the first rolling\n        for k in range(6):\n            dp[0][1][k] = 1\n        \n        mod = 10**9+7\n        # iterate rest n-1 time rollings\n        for i in range(1,n):\n            # for this turn rolling ending with k\n            for k in range(6):\n                #for last turn rolling ending with prev\n                for prev in range(6):\n                    # for last turn ending with continous j number of prev \n                    for j in range(1,min(rollMax[prev],i+1)+1):\n                        if prev == k:\n                            dp[i][j][k]+=dp[i-1][j-1][k]\n                            dp[i][j][k]%=mod\n                        else:\n                            dp[i][1][k]+=dp[i-1][j][prev]\n                            dp[i][1][k]%=mod\n        \n        return sum(dp[n-1][j][k] for k in range(6) for j in range(1,min(n,rollMax[k])+1))%mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = {(i, 1):1 for i in range(6)}\n        for _ in range(1, n):\n            dp2 = {}\n            for r, t in dp:\n                for i in range(6):\n                    if r==i:\n                        if t==rollMax[i]:\n                            continue\n                        else:\n                            dp2[(r, t+1)] = dp[(r, t)]\n                    else:\n                        dp2[(i, 1)] = dp2.get((i, 1), 0)+dp[(r, t)]\n            \n            dp = dp2\n        \n        return sum(dp.values())%(10**9+7)", "from functools import lru_cache\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @lru_cache(maxsize=None)\n        def dfs(left, last, length):\n            if left == 0:\n                if length <= rollMax[last]:\n                    return 1\n                else:\n                    return 0\n            total = 0\n            for i in range(6):\n                if i == last:\n                    if length + 1 <= rollMax[last]:\n                        total += dfs(left - 1, i, length + 1)\n                else:\n                    total += dfs(left - 1, i, 1)\n            return total\n        \n        return dfs(n, -1, 0) % (10 ** 9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @lru_cache(maxsize=None)\n        def dfs(n, i, k):\n            if not n: return 1\n            ans = 0\n            for j in range(6):\n                if i != j: \n                    ans += dfs(n-1, j, 1)\n                elif k+1 <= rollMax[j]: \n                    ans += dfs(n-1, j, k+1)\n                    \n            return ans    \n        \n        ans = sum(dfs(n-1, i, 1) for i in range(6))\n        \n        return ans % 1000000007\n    \n    \n    \n    # https://leetcode.com/problems/dice-roll-simulation/discuss/833495/Python-3-or-DFS-%2B-Memoization-or-Explanation\n", "from functools import lru_cache\nclass Solution:\n   \n    @staticmethod\n    def ans_mod(n):\n        return n % (10**9 + 7)\n    \n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # so we need to think about \n    \n        @lru_cache(None)\n        def roll(val, consec_rolls, rolls_left):\n            if rolls_left == 0:\n                return 1\n            \n            ans = 0\n            \n            if consec_rolls < rollMax[val]:\n                ans += roll(val, consec_rolls +1, rolls_left - 1)\n            \n            # now we consider all other possible rolls but not the same val\n            for i in range(6):\n                if i == val:\n                    continue\n                ans += roll(i, 1, rolls_left - 1)\n            return ans\n    \n        return self.ans_mod(roll(0, 0, n))\n            \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        maxAns = 10**9 + 7\n        krollMax = 15\n        \n        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]\n        # [n+1][6][15+1]\n        \n        for i in range(6):\n            dp[1][i][1] = 1\n        \n        for i in range(2,n+1):\n            for j in range(6):#current dice num\n                for p in range(6): # previous dice num \n                    for k in range(1, krollMax+1):\n                        if j != p: #different than previous dice\n                            if k>rollMax[p]: continue\n                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns\n                        elif k<rollMax[j]:\n                                dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns\n        ans = 0\n        for i in range(6):\n            for j in range(15+1):\n                ans += dp[n][i][j]\n        return ans % maxAns\n                            \n                    \n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        maxAns = 10**9 + 7\n        krollMax = 15\n        \n        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]\n        # [n+1][6][15+1]\n        \n        for i in range(6):\n            dp[1][i][1] = 1\n        \n        for i in range(2,n+1):\n            for j in range(6):#current dice num\n                for p in range(6): # previous dice num \n                    for k in range(1, krollMax+1):\n                        if j != p: #different than previous dice\n                            if k>rollMax[p]: continue\n                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns\n                        else:\n                            if k<rollMax[j]:\n                                dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns\n        ans = 0\n        for i in range(6):\n            for j in range(15+1):\n                ans += dp[n][i][j]\n        return ans % maxAns\n                            \n                    \n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        @lru_cache(maxsize=None)\n        \n        def dfs(n, i, k):\n            if not n: \n                return 1\n            ans = 0\n            for j in range(6):\n                if i != j:\n                    ans += dfs(n-1, j, 1)\n                elif k+1 <= rollMax[j]:\n                    ans += dfs(n-1, j, k+1)\n            return ans\n        \n        return sum(dfs(n-1, i, 1) for i in range(6)) % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        @lru_cache(None)\n        def dp(pos, last, numlast):\n            if pos == n:\n                return 1\n            \n            res = 0\n            \n            for i in range(1,7):\n                if i != last:\n                    res += dp(pos+1, i, 1)\n                elif numlast < rollMax[i-1]:\n                    res += dp(pos+1, last, numlast+1)\n            \n            return res\n        \n        return dp(0,0,0) % (10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @lru_cache(maxsize=None)\n        def dfs(n, i, k):\n            if not n: return 1\n            ans = 0\n            for j in range(6):\n                if i != j:\n                    ans += dfs(n-1, j, 1)\n                elif k+1 <= rollMax[j]:\n                    ans += dfs(n-1, j, k+1)\n            return ans    \n        \n        return sum(dfs(n-1, i, 1) for i in range(6)) % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, roll_max: List[int]) -> int:\n        \n        \n        \n        dices = defaultdict(int, {(-1, 0) : 1}) # previous n, # of consecutive : ways\n        for _ in range(n):\n        \n            prev_dices = tuple(dices.items())\n            dices.clear()\n            \n            for pc, ways in prev_dices:\n                prev, consecutive = pc\n                for r, r_max in enumerate(roll_max):\n                    c = int(r == prev) * consecutive + 1\n                    if c <= r_max:\n                        dices[r, c] += ways\n            \n        return sum(dices.values()) % (10 ** 9 + 7)", "def dfs(curr_index, n, rollMax, prev, d):\n        if curr_index == n:\n            return 1\n        if curr_index > n:\n            return 0\n        if (curr_index, prev) in d:\n            return d[(curr_index, prev)]\n        count = 0\n        for i in range(6):\n            if i!=prev:\n                for repeat in range(1, rollMax[i]+1):\n                    count+=dfs(curr_index+repeat, n, rollMax, i, d)\n            d[(curr_index,prev)] = count\n                \n        return count\n    \nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        d = {}\n        MOD = 1000000007\n        return dfs(0, n, rollMax, -1,d)%MOD", "class Solution:\n    def dieSimulator(self, n: int, roll_max: List[int]) -> int:\n        @lru_cache(maxsize=None)\n        def die_simulator(n, consec_num, consec_count):\n            if n == 0:\n                return 1\n            else:\n                res = 0\n                for i in range(6):\n                    if i == consec_num:\n                        if roll_max[i] > consec_count:\n                            res += die_simulator(n - 1, i, consec_count + 1)\n                    elif roll_max[i] != 0:\n                        res += die_simulator(n - 1, i, 1)\n                return res\n                \n        return die_simulator(n, -1, 0) % (10 ** 9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        def ways(side, already, rolls, mem):\n            key = (side, already, rolls)\n            if key in mem: return mem[key]\n            \n            if already >= rollMax[side]:\n                mem[key] = 0\n                return 0\n\n            if rolls == 0:\n                mem[key] = 1\n                return 1\n            \n            ans = 0\n            ans += ways(side, already+1, rolls-1, mem)\n            for i in range(6):\n                if i == side: continue\n                ans += ways(i, 0, rolls-1, mem)\n\n            mem[key] = ans % (10 ** 9 + 7)\n            return mem[key]\n            \n        ans = 0\n        mem = {}\n        for i in range(6):\n            ans += ways(i, 0, n-1, mem)\n        return ans % (10 ** 9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = {(i, 1): 1 for i in range(6)}\n        for i in range(n - 1):\n            next_dp = collections.Counter()\n            for (d, c), v in list(dp.items()):\n                for cur in range(6):\n                    if cur != d:\n                        next_dp[(cur, 1)] += v\n                    else:\n                        if c + 1 <= rollMax[cur]:\n                            next_dp[(cur, c + 1)] += v\n            dp = next_dp\n        \n        return sum(dp.values()) % (10 ** 9 + 7)\n#         def dfs(m, k, con):\n#             if m == 1: return 1, 1\n#             res = [0, 1]\n#             for i in range(6):\n#                 total, con = dfs(m - 1, i)\n#                 if k == i:\n#                     if con + 1 <= rollMax[i - 1]:\n#                         res[0] += total\n#                         res[1] = con + 1\n#                 else:\n#                     res += total\n        \n#         return sum(dfs(n, i) for i in range(6)) % (10 ** 9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        @lru_cache(maxsize=None)\n        def dfs(c,l,d):\n            nonlocal n\n            nonlocal rollMax\n            \n            \n            if rollMax[l] < d:\n                return 0\n            \n            if c == n:\n                return 1\n            \n            sm = 0\n            \n            for i in range(0,6):\n                sm += dfs(c+1,i,1+d*(i==l))\n                    \n            \n            return sm\n        \n        return dfs(0,-1,0)%(10**9 +7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        def helper(currentIndex, n, rollMax, pre,d):\n            if currentIndex==n:\n                return 1\n            elif currentIndex>n:\n                return 0\n            count = 0\n            if (currentIndex,pre) in d: #if this state is already calculated, return the ans\n                return d[(currentIndex,pre)]\n            for index in range(6):\n                if index!=pre:\n                    for repeat in range(1,rollMax[index]+1):\n                        count+=helper(currentIndex+repeat,n,rollMax,index,d)\n            d[(currentIndex,pre)]=count   #save the computation\n            return count\n        \n        rolledCount = [0]*6  #no rolls made yet\n        MOD = 10**9+7\n        d = {}  #dictionary to save the states\n        return helper(0,n,rollMax,-1,d)%MOD\n    \n\n        \n        \n#         memo = {}\n#         def dfs(last, s,  k):\n#             if k == n:\n#                 return 1\n#             if (last, s, k) not in memo:\n#                 res = 0\n#                 for i in range(6):\n#                     if i == last:\n#                         if s + 1 > rollMax[i]:\n#                             continue\n#                         else:\n#                             res += dfs(i, s+1, k+1)\n#                     else:\n#                         res += dfs(i, 1, k+1)\n#                 memo[last, s, k] = res\n#             return memo[last, s, k]\n        \n        \n#         return dfs(None, 0, 0)%(10**9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = {(i, 1): 1 for i in range(6)}\n        for i in range(n - 1):\n            next_dp = collections.Counter()\n            for (d, c), v in list(dp.items()):\n                for cur in range(6):\n                    if cur != d:\n                        next_dp[(cur, 1)] += v\n                    else:\n                        if c + 1 <= rollMax[cur]:\n                            next_dp[(cur, c + 1)] += v\n            dp = next_dp\n        return sum(dp.values()) % (10 ** 9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        maxAns = 10**9 + 7\n        krollMax = 15\n        \n        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]\n        # [n+1][6][15+1]\n        \n        for i in range(6):\n            dp[1][i][1] = 1\n        \n        for i in range(2,n+1):\n            for j in range(6):#current dice num\n                for p in range(6): # previous dice num \n                    for k in range(1, krollMax+1):\n                        if k>rollMax[p]: continue\n                        if j != p: #different than previous dice\n                            dp[i][j][1] = dp[i][j][1] + dp[i-1][p][k]\n                        elif k<rollMax[j]:\n                                dp[i][j][k+1] = dp[i][j][k+1] + dp[i-1][p][k]\n                                # dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns\n        ans = 0\n        for i in range(6):\n            for j in range(15+1):\n                ans += dp[n][i][j]\n        return ans % maxAns\n                            \n                    \n        \n", "import functools as ft\n\n\nclass Solution:\n    \n    BASE = 10 ** 9 + 7\n    \n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.roll_max = rollMax\n        return self.count(n, 1, 0)\n    \n    @ft.lru_cache(None)\n    def count(self, remaining: int, last_roll: int, streak: int) -> int:\n        if remaining == 0:\n            return 1\n        ans = 0\n        for dice in range(1, 7):\n            if dice == last_roll:\n                if streak >= self.roll_max[last_roll - 1]:\n                    continue\n                ans += self.count(remaining - 1, dice, streak + 1)\n            else:\n                ans += self.count(remaining - 1, dice, 1)\n        return ans % self.BASE", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dp[i][j][k] : ith roll, end with j with consecutive k times\n        MOD = 10 ** 9 + 7\n        rdim = max(rollMax)\n        dp = [[[0] * rdim for _ in range(6)] for _ in range(n)]\n        \n        # init\n        for j in range(6):\n            dp[0][j][0] = 1\n        \n        for i in range(1, n):\n            for j in range(6):\n                for prev in range(6):\n                    for k in range(min(rollMax[prev], i + 1)):\n                        if j == prev and k < rollMax[prev] - 1:\n                            dp[i][j][k + 1] += dp[i - 1][prev][k] % MOD\n                        if j != prev:\n                            dp[i][j][0] += dp[i - 1][prev][k] % MOD\n        \n        return sum(dp[n - 1][j][k] for j in range(6) for k in range(rdim)) % MOD", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10**9 + 7\n        memoi = [[1] + ([0] * (limit - 1)) for limit in rollMax]\n        for _ in range(1, n):\n            sumVal = sum(map(sum, memoi)) % MOD\n            newMemoi = []\n            for face in range(1, 7):\n                limits = []\n                limits.append((sumVal - sum(memoi[face-1])) % MOD)\n                for limit in range(1, rollMax[face-1]):\n                    limits.append(memoi[face-1][limit-1])\n                newMemoi.append(limits)\n            memoi = newMemoi\n        return sum(map(sum, memoi)) % MOD\n", "class Solution:\n    def dieSimulator(self, n: int, R: List[int]) -> int:\n        D, R, S, m = [[0]*7 for _ in range(n)], [0]+R, set(range(1,7)), 10**9 + 7\n        def dfs(L, d):\n            if L >= n: return 1 if L == n else 0\n            c = 0\n            if D[L][d]: return D[L][d]\n            for i in S-{d}:\n                for j in range(1,R[i]+1): c += dfs(L+j,i)\n            D[L][d] = c\n            return c\n        return dfs(0,0) % m", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        max_num = max(rollMax)\n        dp = [[[0]*(max_num+1) for _ in range(6)] for _ in range(n+1)]\n        for j in range(6):\n            dp[1][j][1] = 1\n        for i in range(2,n+1):\n            for j in range(6):\n                for p in range(6):\n                    for k in range(1,max_num+1):\n                        if p != j:\n                            dp[i][j][1] = (dp[i][j][1] + dp[i - 1][p][k])%(10**9+7)\n                        elif k < rollMax[p]:\n                            dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i - 1][p][k])%(10**9+7)\n        ans = 0\n        for j in range(6):\n            for k in range(1,max_num+1):\n                ans = (ans + dp[n][j][k])%(10**9+7)\n        return ans\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        cach = {}\n        def helper(remain,last,rollMax):    \n            if (remain,last) in cach:\n                return cach[(remain,last)]\n            else:\n                if remain==0:\n                    return 1\n                else:\n                    ret = 0\n                    for i in range(6):\n                        if last==i:    \n                            continue\n                        else:\n                            for j in range(rollMax[i]):\n                                if remain-j-1>=0:\n                                    ret += helper(remain-j-1,i,rollMax)\n                cach[(remain,last)] = ret%1000000007\n                return cach[(remain,last)]\n        return helper(n,-1,rollMax)\n", "class Solution:\n    \n        \n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        memo = [[[0 for k in range(16)] for j in range(7)] for i in range(n+1)]\n        result = 0\n        mod = 10 ** 9 + 7 \n        \n        \n        def dfs(n, index, k):\n            if n == 0:\n                return 1\n            if memo[n][index][k] != 0:\n                return memo[n][index][k]\n            result = 0\n            for i in range(6):\n                if i == index:\n                    if rollMax[i] > k:\n                        result += dfs(n-1, i, k+1)\n                else:\n                    result += dfs(n-1, i, 1)\n                    result %= mod\n            memo[n][index][k] = result % mod\n            return memo[n][index][k]\n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        for i in range(6):\n            result += dfs(n-1, i, 1)\n            result %= mod\n        return result % mod \n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n      @lru_cache(None)\n      def count(n,idxCnt):\n        if not n: return 1\n        idx,cnt = idxCnt\n        out = 0\n        for i in range(6):\n          times = rollMax[i]\n          if idx == i:\n            if times >cnt:\n              out+=count(n-1,(i,cnt+1))\n          else:      \n              out+=count(n-1,(i,1))\n        return out \n      return count(n, (0,0))%1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @lru_cache(None)\n        def helper(n, consec):\n            # consec: [0,2] already roll 1 twice\n            if rollMax[consec[0]] < consec[1]:\n                return 0\n            elif n == 0:\n                return 1\n\n            res = []\n            for i in range(1, 7):\n                if i - 1 ==  consec[0]:\n                    res.append(helper(n-1, (consec[0], consec[1] + 1)))\n                else:\n                    res.append(helper(n-1, (i-1, 1)))\n            # print(n , res, sum(res), sum(res) % (10**9+7))\n            return sum(res) % (10**9+7)\n        \n        return helper(n, (0,0))\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        if n < 1:\n            return 0\n        \n        def backtrack(prev_roll, count, seq_len):\n            if seq_len == n:\n                return 1\n            \n            if (prev_roll, count, seq_len) in cache:\n                return cache[(prev_roll, count, seq_len)]\n            result = 0\n\n            for num in range(6):\n                if num != prev_roll:\n                    result += backtrack(num, 1, seq_len+1)\n                elif count < rollMax[num]:\n                    result += backtrack(num, count+1, seq_len+1)\n            \n            cache[(prev_roll, count, seq_len)] = result % MOD\n            return cache[(prev_roll, count, seq_len)]\n        \n        MOD = (10 ** 9) + 7\n        cache = {}\n        return backtrack(-1, 0, 0)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        modVal = 10**9 + 7\n        memo = {}\n        def recurse(numLeft, prevNum, prevNumCount):\n            if numLeft == 0:\n                return 1\n            \n            if (numLeft, prevNum, prevNumCount) in memo:\n                return memo[(numLeft, prevNum, prevNumCount)]\n            \n            numWays = 0\n            for i in range(len(rollMax)):\n                if i == prevNum:\n                    if prevNumCount < rollMax[i]:\n                        numWays += recurse(numLeft - 1, i, prevNumCount + 1)\n                else:\n                    numWays += recurse(numLeft - 1, i, 1)\n            \n            memo[(numLeft, prevNum, prevNumCount)] = numWays % modVal\n            \n            return numWays\n        \n        return recurse(n, -1, -1) % modVal", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        memo, mod = [[0]*6 for _ in range(n)], 10**9+7\n        memo[0] = [1]*6\n        \n        for i in range(1,n):\n            prev_sum = sum(memo[i-1]) % mod\n            for j in range(6):\n                memo[i][j] = prev_sum\n                if i == rollMax[j]:\n                    memo[i][j] -= 1\n                elif i > rollMax[j]:\n                    memo[i][j] = (memo[i][j] - sum(memo[i-rollMax[j]-1]) + memo[i-rollMax[j]-1][j]) % mod\n                \n        return sum(memo[n-1]) % mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]\n        for j in range(len(rollMax)):\n            dp[1][j] = 1\n            dp[1][-1] += dp[1][j]\n        \n        for i in range(2, n + 1):\n            for j in range(len(rollMax)):\n                dp[i][j] = dp[i - 1][-1]\n                k = i - rollMax[j]\n                if k == 1:\n                    dp[i][j] -= 1\n                elif k > 1:\n                    dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])\n                dp[i][-1] += dp[i][j]\n        return dp[n][-1] % int(1e9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        def solve(i, numConsecutive, last):\n            # Base case: finished one iteration\n            if i == n:\n                return 1\n            \n            # Memoization case\n            if (i, numConsecutive, last) in memo:\n                return memo[(i, numConsecutive, last)]\n            \n            # Recursive cases: try every roll as long as it doesn't interfere\n            count = 0\n            \n            for f in range(6):\n                if last != f:\n                    count += solve(i+1, 1, f)\n                \n                elif numConsecutive + 1 <= rollMax[f]:\n                    count += solve(i+1, numConsecutive + 1, last)\n            \n            count %= MOD\n            memo[(i, numConsecutive, last)] = count\n            return count\n        \n        MOD = 10**9 + 7\n        memo = {}\n        return solve(0, 0, -1)", "from functools import lru_cache\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        @lru_cache(None)\n        def roll(val, cons, left):\n            if left == 0: return 1\n            \n            ans = sum([roll(nval, 1, left-1) for nval in range(6) if nval != val])\n            \n            if cons < rollMax[val]:\n                ans += roll(val, cons+1, left-1)\n                \n            return ans\n        \n        return roll(0,0,n) % (10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        mem={}\n        mod=int(10**9)+7\n        \n        def rec(n,li,k):\n            if n==0:\n                return 1\n            elif (n,li,k) in mem:\n                return mem[(n,li,k)]\n            else:\n                ans=0\n                for i in range(6):\n                    if i==li:\n                        if k+1<=rollMax[li]:\n                            ans+=rec(n-1,li,k+1)%mod\n                    else:\n                        ans+=rec(n-1,i,1)%mod\n                mem[(n,li,k)]=ans%mod\n                return ans%mod\n            \n        \n        return rec(n,0,0)%mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        def helper(last,index,maxval):\n            if index==n:\n                return 1\n            \n            val=0\n            \n            if (index,last,maxval) in dp:\n                return dp[(index,last,maxval)]\n            for i in range(6):\n                if last==i:\n                    if maxval+1>rollMax[i]:\n                        continue\n                    else:\n                        val+=helper(i,index+1,maxval+1)\n                else:\n                    val+=helper(i,index+1,1)\n            dp[(index,last,maxval)]= val %(10**9 + 7)\n            return val\n            \n            \n        dp={}\n        return helper(None,0,0)%(10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10**9+7\n        dp = {}\n        \n        def helper(preV, repeat, n0):\n            if n0 == 0:\n                return 1\n            if (preV, repeat, n0) in dp:\n                return dp[(preV, repeat, n0)]\n            \n            subAns = 0\n            for nextV in range(1, 7):\n                if nextV == preV:\n                    if repeat < rollMax[preV-1]:\n                        subAns += helper(preV, repeat+1, n0-1)\n                else:\n                    subAns += helper(nextV, 1, n0-1)\n            dp[(preV, repeat, n0)] = subAns % MOD\n            return dp[(preV, repeat, n0)]\n        return helper(-1, 0, n)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10**9+7\n        dp = {}\n        \n        def helper(preV, repeat, n0):\n            if n0 == 0:\n                return 1\n            if (preV, repeat, n0) in dp:\n                return dp[(preV, repeat, n0)]\n            \n            subAns = 0\n            for nextV in range(1, 7):\n                if nextV == preV:\n                    if repeat < rollMax[preV-1]:\n                        subAns += helper(preV, repeat+1, n0-1)\n                else:\n                    subAns += helper(nextV, 1, n0-1)\n            dp[(preV, repeat, n0)] = subAns % MOD\n            return dp[(preV, repeat, n0)]\n        return helper(-1, 0, n) % MOD", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        memo = {}\n        def dfs(last, s,  k):\n            if k == n:\n                return 1\n            if (last, s, k) not in memo:\n                res = 0\n                for i in range(6):\n                    if i == last:\n                        if s + 1 > rollMax[i]:\n                            continue\n                        else:\n                            res += dfs(i, s+1, k+1)\n                    else:\n                        res += dfs(i, 1, k+1)\n                memo[last, s, k] = res%(10**9 + 7)\n            return memo[last, s, k]\n        return dfs(None, 0, 0)%(10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0 for _ in range(len(rollMax)+1)] for _ in range(n+1)]\n        for j in range(len(rollMax)):\n            dp[1][j] = 1\n            dp[1][-1] += dp[1][j]\n        for i in range(2,n+1):\n            for j in range(len(rollMax)):\n                dp[i][j] = dp[i-1][-1]\n                k = i - rollMax[j]\n                if k == 1:\n                    dp[i][j] -= 1\n                elif k > 1:\n                    dp[i][j] -= (dp[k-1][-1] - dp[k-1][j])\n                dp[i][-1] += dp[i][j]\n        return dp[-1][-1] % int(1e9+7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dp template 2: number of paths\n        \n        \n        cache = {}\n        MOD = 10**9 + 7\n        def dp(n: int, prev_roll: int, prev_count: int) -> int:\n            if n == 0:\n                return 1\n            \n            if (n, prev_roll, prev_count) in cache: # store state\n                return cache[n, prev_roll, prev_count]\n            \n            res = 0\n            for i in range(len(rollMax)):\n                if prev_roll != None and i == prev_roll:\n                    if prev_count == rollMax[i]: # can't be more than rollMax[i] consecutive times\n                        continue\n                    res += dp(n-1, i, prev_count+1)\n                else:\n                    res += dp(n-1, i, 1)\n            \n            cache[n, prev_roll, prev_count] = res % MOD\n            return res % MOD\n        \n        return dp(n, None, None)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        def roll(last,last_num,rolls):\n            if rolls==0:\n                return 1\n            if (last,last_num,rolls) in memo:\n                return memo[(last,last_num,rolls)]\n            tmp = 0\n            for cur in range(1,7):\n                if cur==last:\n                    if last_num+1>rollMax[cur-1]:\n                        continue\n                    tmp += roll(last,last_num+1,rolls-1)\n                else:\n                    tmp += roll(cur,1,rolls-1)\n                tmp = tmp % (10**9 +7)\n            memo[(last,last_num,rolls)] = tmp\n            return tmp\n        \n        \n        memo = {}\n        return roll(-1,0,n)\n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        memo = {}\n        def dfs(last, s,  k):\n            if k == n:\n                return 1\n            if (last, s, k) not in memo:\n                res = 0\n                for i in range(6):\n                    if i == last:\n                        if s + 1 > rollMax[i]:\n                            continue\n                        else:\n                            res += dfs(i, s+1, k+1)\n                    else:\n                        res += dfs(i, 1, k+1)\n                memo[last, s, k] = res%(10**9 + 7)\n            return memo[last, s, k]\n        return dfs(None, 0, 0)%(10**9 + 7)\n", "class Solution:\n    def dieSimulatorLast(self, n, rollMax, last, count):\n        # n: number of rolls\n        # rollMax: \n        # last: the last number in the sequence\n        # count: how many times `last` occurs consecutively in the sequence\n        if count > rollMax[last]:\n            return 0\n        elif n == 0:\n            return 1\n        elif self.result[last][count][n] != -1:\n            return self.result[last][count][n]\n        \n        temp = 0\n        for i in range(6):\n            if i == last:\n                temp += self.dieSimulatorLast(n-1,rollMax,i,count+1)\n            else:\n                temp += self.dieSimulatorLast(n-1,rollMax,i,1)\n        self.result[last][count][n] = temp % 1000000007\n                \n        return temp % 1000000007\n        \n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.result = [[[-1 for i in range(n+1)] for j in range(17)] for k in range(6)]\n        return self.dieSimulatorLast(n, rollMax, 0, 0)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[[0] * (max(rollMax)+1) for x in range(7)] for x in range(n+1)]\n        \n        \n        def dfs(roll,prev,count):\n            \n            if roll == 0:\n                return 1\n            \n            if dp[roll][prev][count] != 0:\n                return dp[roll][prev][count]\n            \n            result = 0\n            for x in range(1,7):\n                if x == prev:\n                    if count < rollMax[x-1]:\n                        result += dfs(roll-1,x,count+1)\n                else:\n                    result += dfs(roll-1,x,1)\n            \n            dp[roll][prev][count] = result\n            return result\n    \n        return dfs(n,0,0) % 1000000007", "def simulatorHelper(n, rollMax, consec, rolls, last, dp):\n    if rolls == n:\n        return 1\n    elif dp[rollMax[last]][consec][rolls] != -1:\n        return dp[rollMax[last]][consec][rolls]\n    else:\n        total = 0\n        for i in range(len(rollMax)):\n            if last == i and consec == rollMax[i]:\n                continue\n            else:\n                if last == i:\n                    total += simulatorHelper(n, rollMax, consec + 1, rolls + 1, i, dp)\n                else:\n                    total += simulatorHelper(n, rollMax, 1, rolls + 1, i, dp)\n        dp[rollMax[last]][consec][rolls] = total\n        return total\ndef simulator(n, rollMax):\n    dp = [[[-1 for rolls in range(n + 1)] for consec in range(16)] for rollMax in range(16)]\n    return simulatorHelper(n, rollMax, 0, 0, 0, dp) % (10 ** 9 + 7)\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        return simulator(n, rollMax)", "#[Runtime: 864 ms, faster than 53.84%] DP(bottom-up)\n#O(6N * 6T): T: upperbound of rollMax\n\n#f(i, d): number of combinations of res[0~i] if the last number is d\n#f(0, ?) = 1\n#                 |------------| <= rollMax[d]\n#               d'd d d ... d [d]\n#               ? d'd d ... d [d]\n#               ? ? d'd ... d [d]\n#               ? ? ? d'... d [d]\n#               ? ? ? ? ... d'[d]\n#f(i, d) = sum{ f(j, d') for j in i-rollMax[d] ~ i-1 for d' in 0~5\n#               if i-rollMax[d] >= 0 and d' != d }\n#          sum{ f(i-1, d') for any d' if i < rollMax[d]} < no limit\n#or\n#total(i) = sum(f(i, d) for d in range(6))\n#f(i, d) = sum( total[j] - f(j, d) for j in i-rollMax[d]~i-1 ) if i >= rollMax[d]\n#          total[i-1] if i < rollMax[d]\nMOD = 1000000007\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * 6 for _ in range(n)]\n        total = [0] * n\n        for d in range(6):\n            dp[0][d] = 1\n        total[0] = sum(dp[0][d] for d in range(6))\n        for i in range(1, n):\n            for d in range(6):\n                if i < rollMax[d]: #no constraint\n                    dp[i][d] = total[i-1]\n                else:\n                    dp[i][d] = sum(total[j] - dp[j][d] for j in range(i-rollMax[d], i)) % MOD\n            total[i] = sum(dp[i][d] for d in range(6)) % MOD\n        return total[n-1]", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        maxAns = 10**9 + 7\n        krollMax = 15\n        \n        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]\n        # [n+1][6][15+1]\n        \n        for i in range(6):\n            dp[1][i][1] = 1\n        \n        for i in range(2,n+1):\n            for j in range(6):#current dice num\n                for p in range(6): # previous dice num \n                    for k in range(1, krollMax+1):\n                        if j != p: #different than previous dice\n                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns\n                        else:\n                            if k<rollMax[j]:\n                                dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns\n        ans = 0\n        for i in range(6):\n            for j in range(15+1):\n                ans += dp[n][i][j]\n        return ans % maxAns\n                            \n                    \n        \n", "class Solution:\n    def dieSimulator(self,n, rollMax):\n        if n==1:\n            return 6\n        mod = int(1e9+7)\n        #naive dp\n        dp = [[[0]*15 for j in range(6)] for i in range(n)]\n        #print(len(dp))\n        #init\n        for i in range(6):\n            dp[0][i][0] = 1\n        #main process\n        for i in range(1,n):\n            for p in range(6):\n                for j in range(6):\n                    for k in range(15):\n                        #update dp[i][j][0]\n                        if p!=j:\n                            dp[i][j][0] = (dp[i][j][0]+dp[i-1][p][k]) % mod\n                        #update dp[i][j][k]\n                        elif k>0 and k<rollMax[j]:\n                            dp[i][j][k] = dp[i-1][j][k-1]\n        ans = 0\n        for j in range(6):\n            for k in range(15):\n                ans = (ans + dp[-1][j][k]) % mod\n        return ans\n", "class Solution:\n    # @lru_cache(None)\n    def __init__(self):\n        self.store = defaultdict(int)\n    def rds(self, n, rm, pre, prec):\n        if n==0:\n            return 1\n        else:\n            if (n, pre, prec) in self.store:\n                return self.store[(n, pre, prec)]\n            else:\n                result = 0\n                for i in range(6):\n                    if i==pre:\n                        if prec<rm[i]:\n                            result+=self.rds(n-1, rm, i, prec+1)\n                    else:\n                        result+=self.rds(n-1, rm, i, 1)\n                result%=1000000007\n                self.store[(n, pre, prec)] = result\n                return result\n    def dieSimulator(self, n: int, rm: List[int]) -> int:\n        res=self.rds(n, rm, None, 0)\n        return res\n                    \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        cache = {}\n        \n        def dfs(rem, last, lastLen):\n            if rem == 0:\n                return 1\n            \n            if (rem, last, lastLen) in cache:\n                return cache[(rem, last, lastLen)]\n            \n            ans = 0\n            for i in range(1, 7):\n                if i == last and lastLen == rollMax[i-1]:\n                    continue\n                ans = (ans + dfs(rem - 1, i, 1 if i != last else lastLen + 1)) % 1000000007\n            if last != -1:\n                cache[(rem, last, lastLen)] = ans\n            \n            return ans\n        \n        return dfs(n, -1, 0)", "class Solution:\n    # @lru_cache(None)\n    def __init__(self):\n        self.store = defaultdict(int)\n    def rds(self, n, rm, pre, prec):\n        if n==0:\n            return 1\n        else:\n            if (n, pre, prec) in self.store:\n                return self.store[(n, pre, prec)]\n            else:\n                result = 0\n                for i in range(6):\n                    if i==pre:\n                        if prec<rm[i]:\n                            result+=self.rds(n-1, rm, i, prec+1)\n                    else:\n                        result+=self.rds(n-1, rm, i, 1)\n                result%=1000000007\n                self.store[(n, pre, prec)] = result\n                return result\n    def dieSimulator(self, n: int, rm: List[int]) -> int:\n        # print(rm)\n        res=self.rds(n, rm, None, 0)\n        return res\n                    \n", "class Solution:\n    def __init__(self):\n        self.store = defaultdict(int)\n        \n    def rds(self, n, rm, pre, prec):\n        if n==0:\n            return 1\n        else:\n            if (n, pre, prec) in self.store:\n                return self.store[(n, pre, prec)]\n            else:\n                result = 0\n                for i in range(6):\n                    if i==pre:\n                        if prec<rm[i]:\n                            result+=self.rds(n-1, rm, i, prec+1)\n                    else:\n                        result+=self.rds(n-1, rm, i, 1)\n                result%=1000000007\n                self.store[(n, pre, prec)] = result\n                return result\n    def dieSimulator(self, n: int, rm: List[int]) -> int:\n        res=self.rds(n, rm, None, 0)\n        return res\n                    \n", "class Solution:\n    # @lru_cache(None)\n    def __init__(self):\n        self.store = defaultdict(int)\n    def rds(self, n, rm, pre, prec):\n        if n==0:\n            return 1\n        else:\n            if (n, pre, prec) in self.store:\n                return self.store[(n, pre, prec)]\n            else:\n                result = 0\n                for i in range(6):\n                    if i==pre:\n                        if prec<rm[i]:\n                            result+=self.rds(n-1, rm, i, prec+1)\n                    else:\n                        result+=self.rds(n-1, rm, i, 1)\n                result%=1000000007\n                self.store[(n, pre, prec)] = result\n                return result\n    def dieSimulator(self, n: int, rm: List[int]) -> int:\n        # print(rm)\n        \n        res = 0\n        for i in range(6):\n            res+=self.rds(n-1, rm, i, 1)\n        return res%1000000007\n                    \n", "from functools import lru_cache\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.rollMax = rollMax\n        return self.solve(n, -1, 0) % (1000000007)\n        \n    @lru_cache(maxsize=4096, typed=False)\n    def solve(self, n, last_index=-1, last_times=0):\n        if n == 0:\n            return 1\n        else:\n            res = 0\n            for i in range(6):\n                if i == last_index and self.rollMax[i] > last_times:\n                    res += self.solve(n - 1, i, last_times + 1)\n                elif i != last_index:\n                    res += self.solve(n - 1, i, 1)\n\n            return res\n", "class Solution:\n    base = 10**9+7\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[1] * rollMax[i] for i in range(6)]\n        \n        for m in range(1, n):\n            s = sum(dp[k][-1] for k in range(6))\n            zero = [s-dp[k][-1] for k in range(6)]\n            \n            for i in range(6):\n                for j in range(rollMax[i]-1,0,-1):\n                    dp[i][j] = (zero[i] + dp[i][j-1]) % self.base\n                dp[i][0] = zero[i] % self.base\n        \n        return sum(dp[i][-1] for i in range(6)) % self.base\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        \n        return self.recur(n,-1,1,rollMax,{}) % (10**9 + 7)\n        \n        \n    \n    def recur(self,n,prev,count,rollMax,op):\n        \n        if (n,prev,count) in op:\n            return op[(n,prev,count)]\n        \n        if n == 0:\n            return 1 \n        else:\n            \n            t = 0\n            for i in range(6):\n                \n                if prev == i:\n                    if count+1 <= rollMax[i]:\n                        t += self.recur(n-1,i,count+1,rollMax,op)\n                        \n                else:\n                    \n                    t += self.recur(n-1,i,1,rollMax,op)\n            \n            op[(n,prev,count)] = t\n            return t \n                    \n                    \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        for i in range(len(rollMax)):\n            rollMax[i] = min(rollMax[i], n)\n        dp = []\n        max_roll = max(rollMax) + 1\n        for k in range(n + 1):\n            dp.append([])\n            for i in range(6):\n                dp[-1].append([])\n                for j in range(max_roll):\n                    if k == 1 and j > 0:\n                        dp[-1][-1].append(1)\n                    else:\n                        dp[-1][-1].append(0)\n\n        MOD = (10 ** 9) + 7\n        for k in range(1, n + 1):\n            for prev_roll in range(6):\n                for cur_roll in range(6):\n                    for j in range(1, max_roll):\n                        if prev_roll == cur_roll:\n                            dp[k][prev_roll][j] += dp[k - 1][prev_roll][j - 1] % MOD\n                        else:\n                            dp[k][prev_roll][j] += dp[k - 1][cur_roll][rollMax[cur_roll]] % MOD\n        ans = 0\n        for i in range(6):\n            ans += dp[n][i][rollMax[i]] % MOD\n        return ans % MOD\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        \n        self.mem = {}\n        def dfs(length, lastnum, lastcount):\n            if length==n:\n                return 1\n            if (length,lastnum,lastcount) in self.mem:\n                return self.mem[(length,lastnum,lastcount)]\n            counts = 0\n            \n            for i,nxt in enumerate('123456'):\n                if lastnum==nxt:\n                    if lastcount<rollMax[i]:\n                        counts+=dfs(length+1, nxt, lastcount+1)\n                else:\n                    counts+= dfs(length+1,nxt,1)\n                    \n            counts = counts%(10**9+7)\n            self.mem[(length,lastnum,lastcount)] = counts\n            return counts\n        \n        lastnum = '0'\n        lastcount=0\n        res = dfs(0,'0',0)\n        \n        return res", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dp[i][j][k] means this is ith roll and we end up with number j and it has lasted k times\n        dp = [[[0 for k in range(16)] for j in range(7)] for i in range(n + 1)]\n        mod = pow(10, 9) + 7\n        \n        for j in range(1, 7):\n            dp[1][j][1] = 1\n        \n        for i in range(2, n + 1):\n            for j in range(1, 7):\n                for k in range(1, 16):\n                    if k != 1:\n                        if k <= rollMax[j - 1]:\n                            dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % mod\n                    else:\n                        for jj in range(1, 7):\n                            if jj != j:\n                                for kk in range(16):\n                                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][jj][kk]) % mod\n        \n        ans = 0\n        for j in range(1, 7):\n            for k in range(1, 16):\n                ans = (ans + dp[n][j][k]) % mod\n        \n        return ans", "class Solution:\n    @lru_cache(maxsize = None)\n    def roll(self, val, consec, left):\n        if left == 0:\n            return 1\n        \n        total = 0\n        \n        for i in range(0,6):\n            if i != val:\n                total += self.roll(i, 1, left-1)\n                \n        if consec < self.rm[val]:\n            total += self.roll(val, consec+1, left-1)\n            \n        return total\n    \n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.rm = rollMax\n        \n        return self.roll(0,0,n) % ((10**9) + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n             dp={}\n             def die(n,i,c):\n                    if n==0:\n                        return 1\n                    if (n,i,c) in dp:\n                        return dp[(n,i,c)]\n                    res=0 \n                    for j in range(6):\n                        if i!=j:\n                            res+=die(n-1,j,1)\n                        elif c<rollMax[j]:\n                                res+=die(n-1,j,c+1)\n                    dp[(n,i,c)]=res\n                    return res \n             return die(n,-1,0)%int(1e9+7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10**9 + 7\n        memoi = {}\n        def numbers(n, prev, prevCount):\n            if n == 0: return 1\n            if (n, prev, prevCount) in memoi: \n                return memoi[n, prev, prevCount]\n            res = 0\n            for face in range(1, 7):\n                if face != prev or rollMax[face-1] > prevCount:\n                    res = (res + numbers(n - 1, face, prevCount * (face == prev) + 1)) % MOD\n            memoi[n, prev, prevCount] = res\n            return res\n        return numbers(n, -1, 0)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[[0 for _ in range(16)] for _ in range(7)] for _ in range(n+1)]\n        mod = 10**9+7\n\n        for i in range(1, n+1):\n            for j in range(1, 7):# \u6295\u63b7\u7684\u6570\n                if(i == 1):# \u7b2c\u4e00\u6b21\u6295\u63b7\n                    dp[i][j][1] = 1\n                    continue\n\n                # \u6570\u5b57 j \u8fde\u7eed\u51fa\u73b0 k \u6b21\n                for k in range(2, rollMax[j-1]+1):\n                    dp[i][j][k] = dp[i-1][j][k-1]\n                \n                # \u524d\u4e00\u6b21\u6295\u51fa\u7684\u6570\u4e0d\u662f j\n                temp = 0\n                for l in range(1, 7):\n                    if(l == j):\n                        continue\n                    for k in range(1, 16):\n                        temp += dp[i-1][l][k]\n                        temp %= mod\n                dp[i][j][1] = temp\n        \n        res = 0\n        for j in range(1, 7):\n            for k in range(1, 16):\n                res += dp[n][j][k]\n                res %= mod\n        return res", "import functools\n\nmod = 10 ** 9 + 7\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        def memo(f):\n            d = defaultdict()\n            \n            def inner(*args):\n                if d.get(args) is None:\n                    d[args] = f(*args)\n                return d[args]\n            return inner\n        \n        @functools.lru_cache(maxsize=n*16)\n        def inner(n, last, last_n):\n            if n == 0:\n                return 1\n            \n            \n            r = list(range(1, 7))\n            \n            if last and last_n >= rollMax[last - 1]:\n                del r[last - 1]\n            \n            res = [\n                inner(n - 1, i, 1 if i != last else last_n + 1) for i in r\n            ]\n            \n            return sum(res)\n        \n        \n        return inner(n, None, None) % mod\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10 ** 9 + 7\n        dp = [[0] * (n + 1) for _ in range(7)]\n        for j in range(1, n + 1):\n            tot = sum(dp[k][j - 1] for k in range(1, 7)) \n            for i in range(1, 7):\n                if j == 1:\n                    dp[i][j] = 1\n                else:\n                    dp[i][j] = tot\n                    if j > rollMax[i - 1] + 1:\n                        dp[i][j] -= sum(dp[k][j - rollMax[i - 1] - 1] for k in range(1, 7) if k != i) - mod\n                    elif j == rollMax[i - 1] + 1:\n                        dp[i][j] -= 1\n                    dp[i][j] %= mod\n        # print(dp)\n        return sum(dp[k][n] for k in range(1, 7)) % mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        \n        \n        def helper(n, last, count):\n            key = (n, last, count)\n            if key in d:\n                return d[key]\n            if n == 0:\n                return 1\n            \n            ans = 0\n            for i in range(6):\n                if i == last and count == rollMax[i]:\n                    continue\n                if i == last:\n                    ans += helper(n - 1, i, count + 1)\n                else:\n                    ans += helper(n - 1, i, 1)\n                \n            d[key] = ans\n            return d[key]\n        d = dict()\n        return helper(n, -1, 0) % (10**9 + 7)", "MOD = int(1e9 + 7)\n\nclass Solution:\n    def get(self, n, d, l):\n        if n == 1:\n            return 5 if l == 0 else 6\n        \n        try:\n            return self.cache[(n, d, l)]\n        except KeyError:\n            ret = 0\n            for e in range(6):\n                if e == d:\n                    if l > 0:\n                        ret += self.get(n - 1, d, l - 1)\n                        ret %= MOD   \n                else:\n                    ret += self.get(n - 1, e, self.limits[e] - 1)\n                    ret %= MOD\n            self.cache[(n, d, l)] = ret\n            return ret\n                \n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.limits = rollMax\n        self.cache = {}\n        \n        for nn in range(2, n - 1 + 1):\n            for d in range(6):\n                for l in range(self.limits[d] - 1 + 1):\n                    self.get(nn, d, l)\n        ret = 0\n        for d in range(6):\n            ret += self.get(n - 1, d, self.limits[d] - 1)\n            ret %= MOD\n        return ret", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        memo ={}\n        \n        def dfs(nLeft, last, curLen):\n            if (nLeft, last, curLen) in memo:\n                return memo[(nLeft, last, curLen)]\n            if nLeft == 0:\n                return 1\n            cnt = 0\n            for i in range(6):\n                if i==last and rollMax[i] == curLen:\n                    continue\n                cnt += dfs(nLeft-1, i, curLen+1 if i==last else 1 )\n            \n            memo[(nLeft, last, curLen)] = cnt\n            return memo[(nLeft, last, curLen)]\n                    \n        return dfs(n, 0, 0)%(10**9+7)\n    \n    \n#         self.res = 0\n        \n        \n#         def dfs(nLeft, last, curLen):\n#             if nLeft == 0:\n#                 self.res += 1\n#                 return\n            \n#             for i in range(6):\n#                 if i==last and rollMax[i] == curLen:\n#                     continue\n#                 dfs(nLeft-1, i, curLen+1 if i==last else 1 )\n#             return\n            \n#         dfs(n, 0, 0)\n        \n#         return self.res\n    \n", "from collections import defaultdict\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        MOD = 10**9 + 7\n        \n        dice = defaultdict(int)\n        mem = {}\n        \n        def helper(i, predie, count):\n            if i == n:\n                return 1\n            \n            if (i,predie,count) in mem:\n                return mem[(i,predie,count)]\n            \n            \n            out = 0\n            for die in range(6):\n                if die == predie and count == rollMax[die]:\n                    continue\n                v, c = die, 1\n                if die == predie:\n                    c = count + 1\n                out += helper(i+1, v, c) \n                    \n            mem[(i,predie,count)] = out % MOD\n                    \n            return mem[(i,predie,count)]\n        \n        \n        \n        return helper(0, -1, -1)\n            \n            \n            \n            \n            \n", "from collections import defaultdict\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = pow(10, 9) + 7\n        rollMax = [0] + rollMax\n        for i in range (len(rollMax)):\n            rollMax [i] = min(n, rollMax[i])\n        \n        cache = defaultdict(int)\n        def dp (last, consec, pos):\n            if pos == n:\n                return 1\n            if (last, consec, pos) in cache:\n                return cache[(last, consec, pos)]\n            ans = 0\n            for i in range (1, 7):\n                if last == i:\n                    if consec < rollMax[i]:\n                        ans += dp(i, consec + 1, pos + 1)\n                else:\n                    ans += dp(i, 1, pos + 1)\n            cache[(last, consec, pos)] = ans \n            return ans\n        \n        return dp(0, 0, 0) % mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        return self.helper(n, rollMax, 0, 0, {}) % MOD\n        \n    def helper(self, n, rollMax, last, times, cache):\n        if (n, last, times) in cache:\n            return cache[(n, last, times)]\n        \n        if n == 0:\n            return 1\n        \n        res = 0\n        for i in range(6):\n            if last != i + 1:\n                res += self.helper(n - 1, rollMax, i + 1, 1, cache)\n            elif rollMax[i] > times:\n                res += self.helper(n - 1, rollMax, last, times + 1, cache)\n                \n        cache[(n, last, times)] = res\n        return res", "from functools import lru_cache\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = {}\n        \n        def roll(value, consecutiveRolls, left):\n            if left == 0:\n                return 1\n            \n            if (value,consecutiveRolls,left) in dp:\n                return dp[value,consecutiveRolls,left]\n            #print(value, consecutiveRolls, left)\n            #if dp[value][consecutiveRolls][left] != -1:\n            #    return dp[value][consecutiveRolls][left]\n            \n            rolls = 0\n            for i in range(6):\n                if i != value:\n                    rolls += roll(i, 1, left-1)\n                else:\n                    if consecutiveRolls < rollMax[i]:\n                        rolls += roll(i, consecutiveRolls+1, left-1)\n            \n            dp[value,consecutiveRolls,left] = rolls\n            \n            return rolls\n        \n        return roll(0,0,n) % (10**9 + 7)\n                    \n", "import functools\n\nmod = 10 ** 9 + 7\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        def memo(f):\n            d = defaultdict()\n            \n            def inner(*args):\n                if d.get(args) is None:\n                    d[args] = f(*args)\n                return d[args]\n            return inner\n        \n        @functools.lru_cache(maxsize=n*n)\n        def inner(n, last, last_n):\n            if n == 0:\n                return 1\n            \n            \n            r = list(range(1, 7))\n            \n            if last and last_n >= rollMax[last - 1]:\n                del r[last - 1]\n            \n            res = [\n                inner(n - 1, i, 1 if i != last else last_n + 1) for i in r\n            ]\n            \n            return sum(res)\n        \n        \n        return inner(n, None, None) % mod\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mode = (10**9 + 7)\n        memo = {}\n        def dfs(prev , s , n):\n            if n == 0:\n                return 1\n            \n            if(prev,s,n) in memo:\n                return memo[(prev,s,n)]\n            \n            else:\n                res = 0\n                for i in range(6):\n                    if i == prev:\n                        if s +  1 > rollMax[i]:\n                            continue\n                        else:\n                            res += dfs(i, s + 1 , n - 1)\n                    \n                    else:\n                        res += dfs(i, 1 , n -1)\n                memo[(prev,s,n)] = res \n                \n            return res\n        \n        return dfs(-1 , 0, n)%mode\n", "# from function\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        res=0\n        mod=10**9+7\n        @lru_cache(maxsize=None)\n        def dfs(n,val,count):\n            if not n:\n                return 1\n            t=0\n            for i in range(6):\n                if i!=val:\n                    t+=dfs(n-1,i,1)\n                elif i==val and  count<rollMax[i]:\n                    t+=dfs(n-1,val,count+1)\n            # t%=mod\n            return t\n        return sum(dfs(n-1,i,1) for i in range(6))%mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = {}\n        \n        def roll(value, consecutiveRolls, left):\n            if left == 0:\n                return 1\n            \n            if (value,consecutiveRolls,left) in dp:\n                return dp[value,consecutiveRolls,left]\n            #print(value, consecutiveRolls, left)\n            #if dp[value][consecutiveRolls][left] != -1:\n            #    return dp[value][consecutiveRolls][left]\n            \n            rolls = 0\n            for i in range(6):\n                if i != value:\n                    rolls += roll(i, 1, left-1)\n                else:\n                    if consecutiveRolls < rollMax[i]:\n                        rolls += roll(i, consecutiveRolls+1, left-1)\n            \n            dp[value,consecutiveRolls,left] = rolls\n            \n            return rolls\n        \n        return roll(0,0,n) % (10**9 + 7)\n                    \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        modVal = 10**9 + 7\n        memo = {}\n        def recurse(numLeft, prevNum, prevNumCount):\n            if numLeft == 0:\n                return 1\n            \n            if (numLeft, prevNum, prevNumCount) in memo:\n                return memo[(numLeft, prevNum, prevNumCount)]\n            \n            numWays = 0\n            for i in range(len(rollMax)):\n                if i == prevNum:\n                    if prevNumCount < rollMax[i]:\n                        numWays += recurse(numLeft - 1, i, prevNumCount + 1)\n                else:\n                    numWays += recurse(numLeft - 1, i, 1)\n            \n            memo[(numLeft, prevNum, prevNumCount)] = numWays\n            \n            return numWays\n        \n        return recurse(n, -1, -1) % modVal", "class Solution:\n    # 2D dp, where count[i][f] indicates the number of ways after i throw and at face f and total[i] indicates the total number of ways after i throw.\n    # count[0][f] = 0 and total[0] = 1.\n    # for each throw, check the number of ways to after ith throw and the end face is f\n    # def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        \n        \n        \n    # DFS with memoization.\n    # State to remember (#throws_left, #repeat, last_face)\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        cache = collections.defaultdict()\n        \n        def dfs(n, repeat, face):\n            if n == 0:\n                return 1\n            elif (n, repeat, face) in cache:\n                return cache[(n, repeat, face)]\n            else:\n                count = 0\n                for f in range(6):\n                    if f != face:\n                        count += dfs(n - 1, 1, f)\n                    else:\n                        if repeat + 1 <= rollMax[f]:\n                            count += dfs(n - 1, repeat + 1, f)\n                cache[(n, repeat, face)] = count\n                return count\n            \n        return sum(dfs(n - 1, 1, f) for f in range(6)) % (10**9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        def rec(die, cons, empty):\n            if empty == 0:\n                return 1\n\n            ans = 0\n            if (die, cons, empty) in dp:\n                return dp[(die, cons, empty)]\n            for r in range(6):\n                if r != die:\n                    ans += rec(r, 1, empty - 1)\n                elif cons < rollMax[die]:\n                    ans += rec(die, cons + 1, empty - 1)\n            dp[(die, cons, empty)] = ans\n            return ans\n        dp = {}\n        return rec(0, 0, n) % (10 ** 9 + 7)\n\n\n# class Solution:\n#     def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n#         def f(n, num, co):\n            \n#             if n == 0:\n#                 return 1\n            \n#             if (n, num, co) in dp:\n#                 return dp[n, num, co]\n            \n#             ans = 0\n#             for i in range(1, 7):\n#                 if i == num and co + 1 <= rollMax[i - 1]:\n#                     ans += f(n - 1, i, co + 1)\n#                 else:\n#                     ans += f(n - 1, i, 1)\n#             dp[n, num, co] = ans\n#             return ans\n\n#         dp = {}\n#         return f(n, 0, 0) % (10 ** 9 + 7)\n\n\n\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mode = (10**9 + 7)\n        memo = {}\n        def dfs(prev , s , n):\n            if n == 0:\n                return 1\n            \n            if(prev,s,n) in memo:\n                return memo[(prev,s,n)]\n            \n            else:\n                res = 0\n                for i in range(6):\n                    if i == prev:\n                        if s +  1 > rollMax[i]:\n                            continue\n                        else:\n                            res += dfs(i, s + 1 , n - 1)\n                    \n                    else:\n                        res += dfs(i, 1 , n -1)\n                memo[(prev,s,n)] = res \n                \n            return res\n        \n        return dfs(0 , 0, n)% mode\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        rollMax.insert(0, None)\n        memo = {}\n        def recurse(curr_n, curr_num, seq_length):\n            if (curr_n, curr_num, seq_length) in memo:\n                return memo[(curr_n, curr_num, seq_length)]\n            \n            if curr_n == n:\n                return 1\n            comb = 0\n            for i in range(1, len(rollMax)):\n                if i == curr_num and rollMax[i] - seq_length > 0:\n                    comb += recurse(curr_n + 1, curr_num, seq_length + 1)\n                elif i != curr_num:\n                    comb += recurse(curr_n + 1, i, 1)\n            memo[(curr_n, curr_num, seq_length)] = comb\n            return comb\n        combs = 0\n        for i in range(1, 7):\n            combs += recurse(1, i, 1)\n        return combs % 1000000007\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        cache = {}\n        \n        @lru_cache(maxsize=None)\n        def dfs(n, i, k):\n            if not n: return 1\n            ans = 0\n            for j in range(6):\n                if i != j: ans += dfs(n-1, j, 1)\n                elif k+1 <= rollMax[j]: ans += dfs(n-1, j, k+1)\n            return ans    \n        return sum(dfs(n-1, i, 1) for i in range(6)) % 1000000007\n", "from functools import lru_cache\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.rollMax = rollMax\n        return self.solve(n, -1, 0) % (1000000007)\n        \n    @lru_cache(maxsize=1024, typed=False)\n    def solve(self, n, last_index=-1, last_times=0):\n        if n == 0:\n            return 1\n        else:\n            res = 0\n            for i in range(6):\n                if i == last_index and self.rollMax[i] > last_times:\n                    res += self.solve(n - 1, i, last_times + 1)\n                elif i != last_index:\n                    res += self.solve(n - 1, i, 1)\n\n            return res\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        def g(n,k):\n            if n < 1: return 0\n            if n == 1: return 1\n            if (n,k) in g_cache:\n                return g_cache[(n,k)]\n            ans = f(n-1) - f(n-rollMax[k-1]-1) + g(n-rollMax[k-1]-1,k)\n            g_cache[(n,k)] = ans\n            return ans\n\n        def f(n):\n            if n < 0 : return 0\n            if n == 0 : return 1\n            if n in f_cache:\n                return f_cache[n]\n            \n            ans = sum([g(n,k) for k in range(1,7)])\n            f_cache[n] = ans\n            return ans\n            \n        g_cache = {}\n        f_cache = {}\n\n        return f(n) % (10 ** 9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        for i in range(len(rollMax)):\n            rollMax[i] = min(rollMax[i], n)\n        dp = []\n        max_roll = max(rollMax) + 1\n        for k in range(n + 1):\n            dp.append([])\n            for i in range(6):\n                dp[-1].append([])\n                for j in range(max_roll):\n                    if k == 1 and j > 0:\n                        dp[-1][-1].append(1)\n                    else:\n                        dp[-1][-1].append(0)\n\n        MOD = (10 ** 9) + 7\n        for k in range(1, n + 1):\n            for prev_roll in range(6):\n                for cur_roll in range(6):\n                    for j in range(1, max_roll):\n                        if prev_roll == cur_roll:\n                            dp[k][prev_roll][j] += dp[k - 1][prev_roll][j - 1]\n                        else:\n                            dp[k][prev_roll][j] += dp[k - 1][cur_roll][rollMax[cur_roll]]\n        ans = 0\n        for i in range(6):\n            ans += dp[n][i][rollMax[i]]\n        return ans % MOD\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = []\n        max_roll = max(rollMax) + 1\n        for k in range(n + 1):\n            dp.append([])\n            for i in range(6):\n                dp[-1].append([])\n                for j in range(max_roll):\n                    if k == 1 and j > 0:\n                        dp[-1][-1].append(1)\n                    else:\n                        dp[-1][-1].append(0)\n\n        MOD = (10 ** 9) + 7\n        for k in range(1, n + 1):\n            for prev_roll in range(6):\n                for cur_roll in range(6):\n                    for j in range(1, max_roll):\n                        if prev_roll == cur_roll:\n                            dp[k][prev_roll][j] += dp[k - 1][prev_roll][j - 1]\n                        else:\n                            dp[k][prev_roll][j] += dp[k - 1][cur_roll][rollMax[cur_roll]]\n        ans = 0\n        for i in range(6):\n            ans += dp[n][i][rollMax[i]]\n        return ans % MOD\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        memo = {}\n        def dfs(last, s,  k):\n            if k == n:\n                return 1\n            if (last, s, k)  in memo:\n                return memo[last, s, k]\n            \n            else:\n                \n                res = 0\n                for i in range(6):\n                    if i == last:\n                        if s + 1 > rollMax[i]:\n                            continue\n                        else:\n                            res += dfs(i, s+1, k+1)\n                    else:\n                        res += dfs(i, 1, k+1)\n                memo[last, s, k] = res\n            return res\n        \n        \n        mode = 10**9 + 7\n        return dfs(None, 0, 0)%mode\n", "from functools import lru_cache\nclass Solution:\n    def __init__(self):\n        self.result = 0\n    \n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @lru_cache(maxsize=None)\n        def helper(last_val: int, streak_count: int, size: int):\n            if size == n:\n                return 1\n            result = 0\n            for i in range(len(rollMax)):\n                if last_val != i:\n                    result += helper(i, 1, size + 1)\n                elif streak_count + 1 <= rollMax[i]:\n                    result += helper(i, streak_count + 1, size + 1)\n            return result\n        return helper(-1, 1, 0) % (10**9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        memo = {}\n        def dfs(last, s,  k):\n            if k == n:\n                return 1\n            if (last, s, k) not in memo:\n                res = 0\n                for i in range(6):\n                    if i == last:\n                        if s + 1 > rollMax[i]:\n                            continue\n                        else:\n                            res += dfs(i, s+1, k+1)\n                    else:\n                        res += dfs(i, 1, k+1)\n                memo[last, s, k] = res\n            return memo[last, s, k]\n        \n        \n        return dfs(None, 0, 0)%(10**9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.mod = 10**9+7\n        self.memo = {}\n\n        def helper(rolls, last, freq):\n            if rolls==0:\n                return 1\n            if (rolls, last, freq) in self.memo:\n                return self.memo[(rolls, last, freq)]\n            count = 0\n            for j in range(len(rollMax)):\n                if j==last:\n                    if freq<rollMax[j]:\n                        count += (helper(rolls-1, j, freq+1))%self.mod\n                else:\n                    count += (helper(rolls-1, j, 1))%self.mod\n            self.memo[(rolls, last, freq)] = count%self.mod\n            return count%self.mod\n        \n        count = 0\n        for i in range(6):\n            count += helper(n-1, i, 1)\n        return count%self.mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[[0]*16 for _ in range(6)]for _ in range(n)]\n        \n        for i in range(6):\n            dp[0][i][1] = 1\n            \n        MOD = 10**9+7\n        \n        for i in range(1, n):\n            for j in range(6):\n                for k in range(6):\n                    if j!=k:\n                        for l in range(16):\n                            dp[i][j][1] += dp[i-1][k][l]\n                            dp[i][j][1] %= MOD\n                    else:\n                        for l in range(rollMax[j]):\n                            dp[i][j][l+1] += dp[i-1][k][l]\n                            dp[i][j][l+1] %= MOD\n        \n        ans = 0\n        \n        for i in range(6):\n            for j in range(16):\n                ans += dp[n-1][i][j]\n                ans %= MOD\n        \n        return ans", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @lru_cache(maxsize=None)\n        \n        # @func DFS: depth-first search on the chance of rolling a given combination\n        # @param n: the number of chances you have left to roll\n        # @param i: the number you roll\n        # @param k: counter for the number of times this number was repeated\n        def DFS(n, i, k):\n            # If there is no more chances left (this is a combination)..\n            if not n:\n                # Count the combintation as a single one\n                return 1\n            \n            # Create a counter to determine the number of possible combintations with this configuration\n            numSequences = 0\n            \n            # For each roll of the die\n            for j in range(6):\n                # If this element is not the one currently rolled..\n                if not i == j:\n                    # Add the combination sequences, of this given i, then j sequence\n                    numSequences += DFS(n - 1, j, 1)\n                \n                # If adding another roll of this element is possible given the constraints..\n                elif k + 1 <= rollMax[j]:\n                    # Add the combintation sequence, of this given i, then i (technically j)\n                    numSequences += DFS(n - 1, j, k + 1)\n            \n            return numSequences\n        \n        return sum(DFS(n - 1, i, 1) for i in range(6)) % 1000000007\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        m = max(rollMax)\n        dp = [[1]+[0]*(m-1) for _ in range(len(rollMax))]\n        MOD = 1e9+7\n        for i in range(1, n):\n            tempSumPrev = [0]*len(rollMax)\n            tempDp = [[0]*m for _ in range(len(rollMax))]\n            totalSumPrev = 0\n            for p in dp:\n                for q in p:\n                    totalSumPrev = (totalSumPrev+q)%MOD\n            for j in range(len(rollMax)):\n                tempDp[j][0] = totalSumPrev-sum(dp[j])\n                for k in range(1, rollMax[j]):\n                    tempDp[j][k] = dp[j][k-1]\n            dp = tempDp\n        return int(sum(q for p in dp for q in p)%MOD)", "class Solution:\n    def __init__(self):\n        self.dp = [] \n        \n    def utility(self, n, rollMax, lastVal, count):\n        if n == 0:\n            return 1\n        \n        if self.dp[n][lastVal][count] is not None:\n            return self.dp[n][lastVal][count]\n        \n        ans=0\n        for i in range(1, 7):\n            if lastVal == i:\n                if rollMax[lastVal-1] > count:\n                    ans += self.utility(n-1, rollMax, lastVal, count+1)\n                else:\n                    continue\n            else:\n                ans += self.utility(n-1, rollMax, i, 1) \n\n            \n        self.dp[n][lastVal][count] = ans % 1000000007\n\n        return self.dp[n][lastVal][count]\n        \n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.dp = [[[None for i in range(16)] for j in range(7)] for k in range(5001)]\n        return self.utility(n, rollMax, -1, 0)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        cache = {}\n        \n        def dfs(c,l,d):\n            nonlocal n\n            nonlocal rollMax\n            \n            key = tuple([c,l,d])\n            \n            if key in cache:\n                return cache[key]\n            \n            if rollMax[l] < d:\n                return 0\n            \n            if c == n:\n                return 1\n            \n            sm = 0\n            \n            for i in range(0,6):\n                sm += dfs(c+1,i,1+d*(i==l))\n                    \n            cache[key] = sm\n            \n            return sm\n        \n        return dfs(0,-1,0)%(10**9 +7)", "from functools import lru_cache\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @lru_cache(None)\n        def helper(rolls, side, count):\n            if not rolls:\n                return 1\n            res = 0\n            for i in range(6):\n                if i != side:\n                    res += helper(rolls - 1, i, 1)\n                elif count + 1 <= rollMax[side]:\n                    res += helper(rolls - 1, side, count + 1)\n            return res\n        return sum(helper(n-1, i, 1) for i in range(6)) % (10 ** 9 + 7)\n", "from functools import lru_cache\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        @lru_cache(None)\n        def roll(val,cons,roll_left):\n            if roll_left == 0:\n                return 1\n            total_ways = 0\n            for i in range(6):\n                if i == val:\n                    continue\n                total_ways += roll(i,1,roll_left-1)\n            if cons < rollMax[val]:\n                total_ways += roll(val,cons+1,roll_left-1)\n            return total_ways\n        \n        return roll(0,0,n) % (10**9 + 7)\n", "sys.setrecursionlimit(100000)\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        @lru_cache(None)\n        def f(n, last, consec):\n            if n == 0: return 1\n            if consec < rollMax[last]:\n                A = f(n-1, last, consec+1)\n            else:\n                A = 0\n            return (A + sum(f(n-1, i, 1) for i in range(6) if i != last)) % (10**9+7)\n        return f(n, 0, 0)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[[0 for k in range(16)]for j in range(6)]for i in range(5000)]\n        \n        M = 10 ** 9 + 7\n        \n        def dfs(dies, last, cur_len):\n            if not dies:\n                # print(curr_roll)\n                return 1\n            \n            if last >= 0 and dp[dies][last][cur_len] > 0:\n                return dp[dies][last][cur_len]\n            \n            ret = 0\n            \n            for i in range(6):\n                if cur_len == rollMax[i] and i == last:\n                    continue\n                \n                nxt = 0\n                \n                if last == i:\n                    nxt = cur_len + 1\n                else:\n                    nxt = 1\n                    \n                ret += dfs(dies - 1, i, nxt)\n                ret %= M\n                \n            if last >= 0:\n                dp[dies][last][cur_len] = ret\n            \n            return ret\n        \n        return dfs(n, -1, 0)", "class Solution:\n    def dieSimulator(self, N: int, rollMax: List[int]) -> int:\n        \n        def dp(curr_cnt, curr, n):\n            # print (curr_cnt, curr,n, rollMax[curr-1], curr_cnt)\n            if curr>0 and rollMax[curr-1]<curr_cnt:\n                return 0\n            elif n==0:\n                return 1\n            elif (curr_cnt, curr, n) in memo:\n                return memo[(curr_cnt, curr, n)]\n            else:\n                res = 0\n                for i in range(1, 7):\n                    if i==curr:\n                        res += dp(curr_cnt+1, i, n-1)\n                    else:\n                        res += dp(1, i, n-1)\n                memo[(curr_cnt, curr, n)] = res\n                return res\n            \n        memo = dict()\n        res = dp(0, 0, N)\n        return res%(10**9+7)\n", "from functools import lru_cache\nclass Solution:\n    def dieSimulator(self, n, roll_max):\n\n        dicti = {}\n        \n        def dp(roll, last, count):\n            if not roll:\n                return 1\n            elif (roll, last, count) in dicti:\n                return dicti[(roll, last, count)]\n            \n            ans = 0\n            for i in range(6):\n                if i != last:\n                    ans += dp(roll-1, i, 1)\n                elif count < roll_max[i]:\n                    ans += dp(roll-1, last, count+1)\n            dicti[roll, last, count] = ans % (10**9 + 7)\n            return dicti[roll, last, count]\n        return dp(n, -1, 0)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        cache = {}\n        \n        def dfs(c,l,d):\n            nonlocal n\n            nonlocal rollMax\n            \n            key = tuple([c,l,d])\n            \n            if key in cache:\n                return cache[key]\n            \n            if c == n:\n                return 1\n            \n            sm = 0\n            \n            for i in range(0,6):\n                if i != l or d != rollMax[i]:\n                    sm += dfs(c+1,i,1+d*(i==l))\n                    \n            cache[key] = sm\n            \n            return sm\n        \n        return dfs(0,-1,0)%(10**9 +7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        maxv = max(rollMax)\n        dp = [[[0] * (maxv + 1) for _ in range(6)] for _ in range(n + 1)]\n        \n        for j in range(6):\n            dp[1][j][1] = 1\n        prev_total = 6\n            \n        for n in range(2, n + 1):\n            new_total = 0\n            for roll_num in range(6):\n                one = prev_total - sum(dp[n - 1][roll_num])\n                dp[n][roll_num][1] = one % 1000000007\n                for k in range(2, rollMax[roll_num] + 1):\n                    dp[n][roll_num][k] = dp[n - 1][roll_num][k - 1]\n                new_total += sum(dp[n][roll_num])\n            prev_total = new_total\n        return sum(sum(dp[-1][number]) for number in range(6)) % 1000000007", "from functools import lru_cache\nclass Solution:\n    def dieSimulator(self, n, roll_max):\n\n        dicti = {}\n        \n        def dp(roll, last, count):\n            if not roll:\n                return 1\n            elif (roll, last, count) in dicti:\n                return dicti[roll, last, count]\n            \n            ans = 0\n            for i in range(6):\n                if i != last:\n                    ans += dp(roll-1, i, 1)\n                elif count < roll_max[i]:\n                    ans += dp(roll-1, last, count+1)\n            dicti[roll, last, count] = ans % (10**9 + 7)\n            return dicti[roll, last, count]\n        return dp(n, -1, 0)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.memo = defaultdict(int) # (n, prev) -> bool\n        self.ans = 0\n        def helper(n, prev, m):\n            if n == 0:\n                return 1\n            if self.memo[(n,prev,m)] > 0: \n                return self.memo[(n,prev,m)]\n            ans = 0\n            for i in range(6):\n                if prev == i:\n                    if m >= rollMax[i]:\n                        continue\n                \n                    ans += helper(n-1, i, m+1)\n                else:\n                    ans += helper(n-1, i, 1)\n            self.memo[(n,prev,m)] = ans\n            return ans\n        return helper(n, -1, 0) % (10**9 + 7)\n", "from functools import lru_cache\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.rollMax = rollMax\n        return self.solve(n, -1, 0) % (1000000007)\n        \n    @lru_cache(maxsize=4096 * 2, typed=False)\n    def solve(self, n, last_index=-1, last_times=0):\n        if n == 0:\n            return 1\n        else:\n            res = 0\n            for i in range(6):\n                if i == last_index and self.rollMax[i] > last_times:\n                    res += self.solve(n - 1, i, last_times + 1)\n                elif i != last_index:\n                    res += self.solve(n - 1, i, 1)\n\n            return res\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        return self.dieSimulator_recursive(n, rollMax)\n    \n    def dieSimulator_recursive(self, n: int, rollMax: List[int]) -> int:\n        if n == 0:\n            return 0\n        \n        memo = {}\n        def f(n, d, r):\n            if n == 1:\n                return 1\n            \n            if (n, d, r) in memo:\n                return memo[(n, d, r)]\n            \n            total = 0\n            for nd in range(6):\n                if nd != d:\n                    total += f(n - 1, nd, 1)\n            if r < rollMax[d]:\n                total += f(n - 1, d, r + 1)\n            \n            memo[(n, d, r)] = total\n            return total % (10**9 + 7)\n        \n        total = 0\n        for d in range(6):\n            total += f(n, d, 1)\n        return total % (10**9 + 7)\n\n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        if n == 0:\n            return 0\n        \n        memo = {}\n        def f(d, r, n):\n            if n == 1:\n                return 1\n            \n            if (d, r, n) in memo:\n                return memo[(d, r, n)]\n            \n            total = 0\n            for nd in range(6):\n                if nd != d:\n                    total += f(nd, 1, n - 1)\n            if r < rollMax[d]:\n                total += f(d, r + 1, n - 1)\n            \n            memo[(d, r, n)] = total\n            return total % (10**9 + 7)\n        \n        total = 0\n        for d in range(6):\n            total += f(d, 1, n)\n        return total % (10**9 + 7)\n                    \n                    \n            \n        f = [None] * n\n        for i in range(0, n):\n            f[i] = [None] * 6\n            for d in range(6):\n                if i == 0:\n                    f[i][d] = [1] * rollMax[d]\n                    continue\n                    \n                f[i][d] = [0] * rollMax[d]\n                for r in range(rollMax[d]):\n                    f[i][d][r] += f[i-1][d][r-1] if r-1 >= 0 else 0\n                \n                for r in range(rollMax[d]):\n                    for nd in range(6):\n                        if nd != d:\n                            f[i][d][r] += f[i-1][nd][0]\n                            \n        total = 0\n        for d in range(len(f[n-1])):\n            total += f[n-1][d][rollMax[d]-1]\n        return total\n                \n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # imagine blank spaces equal to \n        # the number of rolls\n        \n        # _ _ _ _ \n        \n        # every time we roll, it could be any of 1-6 numbers\n        \n        # so imagine the first number is 1\n        # what are possibilities for the rest\n        # the rest can again be\n        \n        # what do we want function to return.\n        # instead of returning, can just increment count when reaching the end\n        \n        cache = {}\n        \n        def sim(n, count, curr_element):    \n            if curr_element:\n                if count > rollMax[curr_element-1]:\n                    return float('inf')\n                \n            if (n,count,curr_element) in cache:\n                return cache[(n,count,curr_element)]\n            \n            if n==0:\n                return 1\n\n            # basically how many ways can I reach end from current point\n            all_ans = 0\n            for i in range(1,7):\n                if curr_element == i:\n                    ans = sim(n-1, count+1, i)\n                else:\n                    ans = sim(n-1, 1, i)\n                    \n                if ans!=float('inf'):\n                    all_ans += ans \n                    \n            cache[(n,count, curr_element)] = all_ans\n            return all_ans\n                \n        \n        return sim(n, 0, 0) % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        memo = {}\n        def f(d, r, n):\n            if n == 1:\n                return 1\n            \n            if (d, r, n) in memo:\n                return memo[(d, r, n)]\n            \n            total = 0\n            for nd in range(6):\n                if nd != d:\n                    total += f(nd, 1, n - 1)\n            if r < rollMax[d]:\n                total += f(d, r + 1, n - 1)\n            \n            memo[(d, r, n)] = total\n            return total % (10**9 + 7)\n        \n        total = 0\n        for d in range(6):\n            total += f(d, 1, n)\n        return total % (10**9 + 7)\n                    \n                    \n            \n        f = [None] * n\n        for i in range(0, n):\n            f[i] = [None] * 6\n            for d in range(6):\n                if i == 0:\n                    f[i][d] = [1] * rollMax[d]\n                    continue\n                    \n                f[i][d] = [0] * rollMax[d]\n                for r in range(rollMax[d]):\n                    f[i][d][r] += f[i-1][d][r-1] if r-1 >= 0 else 0\n                \n                for r in range(rollMax[d]):\n                    for nd in range(6):\n                        if nd != d:\n                            f[i][d][r] += f[i-1][nd][0]\n                            \n        total = 0\n        for d in range(len(f[n-1])):\n            total += f[n-1][d][rollMax[d]-1]\n        return total\n                \n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        memo = {}\n        # @lru_cache(None)\n        def helper(n, consec):\n            # consec: [0,2] already roll 1 twice\n            if rollMax[consec[0]] < consec[1]:\n                return 0\n            elif n == 0:\n                return 1\n            elif (n, consec) in memo:\n                return memo[(n, consec)]\n\n            res = []\n            for i in range(1, 7):\n                if i - 1 ==  consec[0]:\n                    res.append(helper(n-1, (consec[0], consec[1] + 1)))\n                else:\n                    res.append(helper(n-1, (i-1, 1)))\n            # print(n , res, sum(res), sum(res) % (10**9+7))\n            memo[(n,consec)] = sum(res) % (10**9+7)\n            return memo[(n,consec)]\n        \n        return helper(n, (0,0))\n", "from functools import lru_cache\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n       \n        \n        @lru_cache(None)\n        def r(v,p,c):\n            if c==n:\n                return 1\n            else:\n                t = 0\n                for i in range(0,6):\n                    if i==p:\n                        if v<rollMax[i]:\n                            t+=r(v+1,i,c+1)\n                    else:\n                        t+=r(1,i,c+1)\n                        \n                return t\n            \n        return r(0,0,0)%(10**9 + 7)", "from random import randint\n\nmod = 10 ** 9 + 7\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        def memo(f):\n            d = defaultdict()\n            \n            def inner(*args):\n                if d.get(args) is None:\n                    d[args] = f(*args)\n                return d[args]\n            return inner\n        \n        @memo\n        def inner(n, last, last_n):\n            if n == 0:\n                return 1\n            \n            \n            r = list(range(1, 7))\n            \n            if last and last_n >= rollMax[last - 1]:\n                del r[last - 1]\n            \n            res = [\n                inner(n - 1, i, 1 if i != last else last_n + 1) for i in r\n            ]\n            \n            return sum(res)\n        \n        \n        return inner(n, None, None) % mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # imagine blank spaces equal to \n        # the number of rolls\n        \n        # _ _ _ _ \n        \n        # every time we roll, it could be any of 1-6 numbers\n        \n        # so imagine the first number is 1\n        # what are possibilities for the rest\n        # the rest can again be\n        \n        # what do we want function to return.\n        # instead of returning, can just increment count when reaching the end\n        \n        self.count = 0\n        cache = {}\n        \n        def sim(n, count, curr_element):    \n            if curr_element:\n                if count > rollMax[curr_element-1]:\n                    return float('inf')\n                \n            if (n,count,curr_element) in cache:\n                return cache[(n,count,curr_element)]\n            \n            if n==0:\n                self.count  +=1\n                return 1\n\n            # basically how many ways can I reach end from current point\n            all_ans = 0\n            for i in range(1,7):\n                if curr_element == i:\n                    ans = sim(n-1, count+1, i)\n                else:\n                    ans = sim(n-1, 1, i)\n                    \n                if ans!=float('inf'):\n                    all_ans += ans \n                    \n            cache[(n,count, curr_element)] = all_ans\n            #print (n,count,curr_element)\n            return all_ans\n                \n        #print (sim(n, 0, 0))\n        \n        return sim(n, 0, 0) % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.memo = [[[0 for k in range(16)] for j in range(6)] for i in range(5001)]\n        def helper(n, prev, m):\n            if n == 0:\n                return 1\n            if self.memo[n][prev][m] > 0: \n                return self.memo[n][prev][m]\n            ans = 0\n            for i in range(6):\n                if prev == i:\n                    if m >= rollMax[i]:\n                        continue\n                \n                    ans += helper(n-1, i, m+1)\n                else:\n                    ans += helper(n-1, i, 1)\n            self.memo[n][prev][m] = ans\n            return ans\n        return helper(n, -1, 0) % (10**9 + 7)\n", "M = int(1e9 + 7)\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        self.roll_max = rollMax\n        self.cache = {}\n        return self._dfs(n, -1, 0)\n    \n    def _dfs(self, rolls_left: int, prev_roll: int, curr_len: int) -> None:\n        if rolls_left == 0:\n            return 1\n        \n        if (rolls_left, prev_roll, curr_len) in self.cache:\n            return self.cache[(rolls_left, prev_roll, curr_len)]\n        \n        result = 0\n        for i in range(6):\n            if i == prev_roll and curr_len >= self.roll_max[i]:\n                continue\n                \n            result += self._dfs(rolls_left - 1, i, curr_len + 1 if i == prev_roll else 1)\n\n        result %= M \n        self.cache[(rolls_left, prev_roll, curr_len)] = result\n        return result\n        \n        \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        if n == 1:\n            return 6\n        mem = {}\n        def get_dp(n, d, c):\n            if n==1:\n                return 6 if c < rollMax[d-1] else 5\n            elif (n, d, c) not in mem:\n                mem[n, d, c] = 0\n                for d_ in range(1, 7):\n                    if d_ != d:\n                        mem[n, d, c] += get_dp(n-1, d_, 1)\n                    elif c < rollMax[d-1]:\n                        mem[n, d, c] += get_dp(n-1, d, c+1)\n            return mem[n, d, c]\n        result = sum(get_dp(n-1, d, 1) for d in range(1, 7))\n        result = result % int(10**9+7)\n        return result", "from functools import lru_cache\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        @lru_cache(maxsize=None)\n        def dfs(left, numConsecutive, last):\n            total = 0\n            if left == 0:\n                if numConsecutive <= rollMax[last]:\n                    return 1\n                else:\n                    return 0\n            for i in range(6):\n                if i == last:\n                    if numConsecutive + 1 <= rollMax[last]:\n                        total += dfs(left - 1, numConsecutive + 1, i)\n                else:\n                    total += dfs(left - 1, 1, i)\n            return total \n        \n        return dfs(n, 0, -1) % (10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        m=max(rollMax)\n        dp=[[0 for i in range(m)] for j in range(6)]\n        for i in range(6):\n            dp[i][0]=1\n        total=6\n        for i in range(n-1):\n            new_dp=[[0 for i in range(m)] for j in range(6)]\n            new_total=0\n            for j in range(6):\n                new_dp[j][0]=total-sum(dp[j])\n                new_dp[j][0]%=(10**9+7)\n                new_total+=new_dp[j][0]\n                new_total%=(10**9+7)\n                for k in range(1,rollMax[j]):\n                    new_dp[j][k]=dp[j][k-1]\n                    new_total+=new_dp[j][k]\n            dp=new_dp\n            total=new_total%(10**9+7)\n        return total%(10**9+7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[1 for _ in range(6)] for _ in range(n)]\n    \n        for i in range(1, n):\n            for j in range(6):\n                inc = sum(dp[i-1])\n                prev = i - rollMax[j] - 1\n                if prev == -1:\n                    inc -= 1\n                elif prev >= 0:\n                    for k in range(6):\n                        if k == j:\n                            continue\n                        inc -= dp[prev][k]\n                dp[i][j] = inc\n        # print(dp)\n        return sum(dp[-1]) % (10 ** 9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        N = n\n        faces = len(rollMax)\n        MOD = 7 + 10**9\n        \n        dp = [[0 for _ in range(faces+1)] for _ in range(N+1)]\n        \n        dp[0][faces] = 1\n        \n        for i in range(faces):\n            dp[1][i] = 1\n        \n        dp[1][faces] = faces\n        \n        for i in range(2, N+1):\n            for j in range(faces):\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    \n                    dp[i][j] += dp[i-k][faces] - dp[i-k][j]\n            \n            dp[i][faces] = sum(dp[i]) % MOD\n        \n        return dp[N][faces] % MOD", "MOD = int(1e9 + 7)\n\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp: List[List[int]] = [[0] * 6 for _ in range(n)]\n        sums: List[int] = [0] * n\n            \n        # Init\n        for j in range(6):\n            dp[0][j] = 1\n            \n        sums[0] = sum(dp[0])\n        \n        # DP\n        for i in range(1, n):\n            for j in range(6):\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        dp[i][j] += 1\n                        break\n\n                    dp[i][j] += sums[i - k] - dp[i - k][j]\n                    \n            sums[i] = sum(dp[i]) % MOD\n            \n        return sums[-1]\n   \n# roll_max_2 = 3\n# _, _, _, 2 = (_, _, !2, 2) + (_, !2, 2, 2) + (!2, 2, 2, 2)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # O(n + sum(rollMax))\n        if n == 1: return 6\n        states = []\n        for i in rollMax:\n            states.append([0]*i)\n            states[-1][0] = 1\n        \n        sums = [0] * 6\n        for i in range(1, n):\n            for i in range(6):\n                sums[i] = sum(states[i])\n            \n            for i in range(6):\n                for j in reversed(list(range(len(states[i])))):\n                    if j == 0:\n                        states[i][0] = sum([sums[index] for index in range(6) if index != i]) % (10**9 + 7)\n                    \n                    else:\n                        states[i][j] = states[i][j-1]\n        \n        return sum([sum(x) for x in states]) % (10**9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        M = 10**9+7\n        memo = [[0]*sum(rollMax) for _ in range(n)]\n        start = {0:0}\n        for i in range(1, len(rollMax)):\n            start[i] = start[i-1] + rollMax[i-1]\n            \n        \n        \n        for i in range(len(rollMax)):\n            s = start[i]\n            memo[0][s] = 1\n        \n        for i in range(1, n):\n            for j in range(len(rollMax)):\n                s = start[j]\n                e = start[j] + rollMax[j]-1\n                memo[i][s] = (sum(memo[i-1][:s])+sum(memo[i-1][e+1:])) % M\n                for k in range(1,rollMax[j]):\n                    memo[i][s+k] = memo[i-1][s+k-1]\n        \n        return sum(memo[-1]) % M\n", "from typing import List\n\nimport numpy\n\n\nclass Solution:\n  def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n    result = 0\n    dims = (n + 1, 7)\n    dp = numpy.zeros(dims, dtype=int)\n    sums = [0] * (n + 1)\n    kMod = 10 ** 9 + 7\n    for j in range(0, 6):\n      dp[1][j] = 1\n      sums[1] += dp[1][j]\n\n\n    for i in range(2, n+1):\n      for j in range(6):\n        k = i - rollMax[j]\n        if k <= 1:\n          invalid = max(k, 0)\n        else:\n          invalid = sums[k - 1] - dp[k-1][j]\n\n        dp[i][j] = ((sums[i - 1] - invalid) % kMod + kMod) % kMod\n        sums[i] = (sums[i] + dp[i][j]) % kMod\n        pass\n      pass\n\n    return sums[-1]\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        m = max(rollMax)\n        dp = [[[1]*m for _ in range(len(rollMax))] for _ in range(n)]\n        dp[0] = [[1]+[0]*(m-1) for _ in range(len(rollMax))]\n        MOD = 1e9+7\n        sumPrev = [1]*len(rollMax)\n        for i in range(1, n):\n            tempSumPrev = [0]*len(rollMax)\n            totalSumPrev = 0\n            for p in sumPrev:\n                totalSumPrev = (totalSumPrev+p)%MOD\n            for j in range(len(rollMax)):\n                dp[i][j][0] = totalSumPrev-sumPrev[j]\n                s=dp[i][j][0]%MOD\n                for k in range(1, rollMax[j]):\n                    dp[i][j][k] = dp[i-1][j][k-1]\n                    s = (s+dp[i][j][k])%MOD\n                tempSumPrev[j] = s\n            sumPrev = tempSumPrev\n        return int(sum(sumPrev)%MOD)", "class Solution:\n    def dieSimulator(self,n, rollMax):\n        if n==1:\n            return 6\n        mod = int(1e9+7)\n        #init\n        dp = [[0]*6 for i in range(n)]\n        for j in range(6):\n            dp[0][j] = 1\n        sums = [0]*n\n        sums[0] = 6\n        #main process\n        for i in range(1,n):\n            #base case\n            #sums[i-1]\n            for j in range(6):\n                invalid = 0\n                k = i-rollMax[j]\n                if k==0:\n                    invalid = 1\n                elif k>0:\n                    invalid = sums[k-1] - dp[k-1][j]\n                dp[i][j] = ((sums[i-1]-invalid)%mod+mod) % mod\n                sums[i] = (sums[i] + dp[i][j]) % mod\n        return sums[-1]", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0 for i in range(6)] for j in range(n)]\n        for i in range(6):\n            dp[0][i] = 1\n        for i in range(1,n):\n            total = sum(dp[i-1])\n            for j in range(6):\n                dp[i][j] += total\n                if i-rollMax[j] == 0:\n                    dp[i][j] -= 1\n                if i-rollMax[j] > 0:\n                    dp[i][j] -= sum(dp[i-rollMax[j]-1]) - dp[i-rollMax[j]-1][j]\n        return sum(dp[n-1])%(10**9+7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        arr = []\n        while n > 0:\n            if not arr:\n                arr.append([1 for _ in range(6)])\n            else:\n                cur_turn = [0 for _ in range(6)]\n                for i in range(6):\n                    if rollMax[i] > len(arr):\n                        cur_turn[i] = sum(arr[-1])\n                    else:\n                        for k in range(1, 1+rollMax[i]):\n                            cur_turn[i] += sum(arr[-k]) - arr[-k][i]\n                cur_turn = [c % (10**9 + 7) for c in cur_turn]\n                arr.append(cur_turn)\n            n -= 1\n        \n        return sum(arr[-1]) % (10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        dp = [[0] * (faces + 1) for _ in range(n + 1)]\n        mod = 10 ** 9 + 7\n        dp[0][faces] = 1\n        \n        for i in range(faces):\n            dp[1][i] = 1\n        dp[1][faces] = faces\n        \n        \n        for i in range(2, n+1):\n            for j in range(faces):\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += (dp[i-k][faces] - dp[i-k][j]) % mod\n                    \n            dp[i][faces] = sum(dp[i][:faces]) % mod\n        \n        return dp[n][faces] % mod\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10**9+7\n        def memo(f):\n            dic = {}\n\n            def f_alt(*args):\n                if args not in dic:\n                    dic[args] = f(*args)\n                return dic[args]\n            return f_alt\n\n        @memo\n        def find_answer(n, l):\n            if n == 1:\n                return 1\n            if n <= 0:\n                return 0\n            return (find(n-1) - (find(n-rollMax[l]-1) - find_answer(n-rollMax[l]-1, l)))%mod\n\n        @memo\n        def find(n):\n            if n == 0:\n                return 1\n            if n < 0:\n                return 0\n            return sum(find_answer(n, r) for r in range(6)) %mod\n\n        return find(n)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        dp = [[0] * (faces+1) for _ in range(n+1)]\n        mod = 10 ** 9 + 7\n        dp[0][faces] = 1\n        \n        for i in range(faces):\n            dp[1][i] = 1\n            \n        dp[1][faces] = faces\n        for i in range(2, n+1):\n            for j in range(faces):\n                for k in range(1, rollMax[j]+1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += (dp[i-k][faces] - dp[i-k][j]) % mod\n            dp[i][faces] = sum(dp[i][:faces]) % mod\n        return dp[n][faces] % mod\n                    \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp=[[1]*6 for _ in range(n)]\n        #dp[i][j]\u4ee3\u8868\u957f\u5ea6\u4e3ai\u7684\u5e8f\u5217\uff0c\u7ed3\u5c3e\u4e3aj\u7684\u7ec4\u5408\u6570\u76ee\n        #\u5f97\u5230\u6240\u6709\u7ec4\u5408\u51cf\u53bb\u4e0d\u7b26\u5408\u89c4\u5219\u7684\n        for i in range(1,n):\n            for j in range(6):\n                dp[i][j]=sum(dp[i-1])\n                if i==rollMax[j]:  #\u6b64\u65f6\u8fde\u7740\u6709j\u9879\n                    dp[i][j]-=1\n                if i>rollMax[j]:\n                    for k in range(6):\n                        if k!=j:\n                            dp[i][j]-=dp[i-1-rollMax[j]][k]\n        return sum(dp[-1])%(10**9+7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10**9 + 7\n        # dp[i][j] records the value of sequence of i elements with j being the last element\n        dp = [[0]*7 for _ in range(n+1)]\n        # initialize\n        dp[0][6] = 1\n        for i in range(6):\n            dp[1][i] = 1\n        dp[1][6] = 6\n        for i in range(2,n+1):\n            for j in range(6):\n                for k in range(1,min(rollMax[j],i)+1):\n                    dp[i][j] += dp[i-k][6]-dp[i-k][j]\n                    dp[i][j] %= mod\n            dp[i][6] = sum([dp[i][j] for j in range(6)])\n            dp[i][6] %=mod\n        return dp[n][6]\n            \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MODE = 1e9+7\n        f = [[0 for _ in range(7)] for _ in range(n+1)]\n        f[0][6] = 1\n        for i in range(1, n + 1):\n            for j in range(6):\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    f[i][j] = (f[i][j] + (f[i-k][6] - f[i-k][j])%MODE)%MODE\n                f[i][6] = (f[i][j] + f[i][6])%MODE\n        return int(f[n][-1])", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * 7 for _ in range(n+1)]\n        ans = 1\n        for i in range(1, n+1):\n            temp = 0\n            for j, r in enumerate(rollMax):\n                if i - r > 1:\n                    dp[i][j] = ans - dp[i-r-1][-1] + dp[i-r-1][j]\n                elif i - r == 1:\n                    dp[i][j] = ans - 1\n                else:\n                    dp[i][j] = ans\n                temp += dp[i][j]\n            dp[i][-1] = temp\n            ans = temp\n        # print(sum(dp[4]))\n        # print(dp)\n        return temp % int(1e9 + 7)\n#         dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]\n#         for j in range(len(rollMax)):\n#             dp[1][j] = 1\n#             dp[1][-1] += dp[1][j]\n        \n#         for i in range(2, n + 1):\n#             for j in range(len(rollMax)):\n#                 dp[i][j] = dp[i - 1][-1]\n#                 k = i - rollMax[j]\n#                 if k == 1:\n#                     dp[i][j] -= 1\n#                 elif k > 1:\n#                     dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])\n#                 dp[i][-1] += dp[i][j]\n#         print(dp)\n#         return dp[n][len(rollMax)] % int(1e9 + 7)\n# [[0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 6], [5, 5, 5, 6, 6, 6, 33], [28, 28, 28, 32, 32, 33, 181], [153, 153, 153, 176, 176, 180, 991], [838, 838, 838, 964, 964, 986, 5428]]\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        Q = [[0 for j in range(7)] for i in range(n+1)]\n        Q[0][-1]=1\n        MAX = 10**9+7\n        for i in range(1,n+1):\n            for j in range(6):\n                if i<=rollMax[j]:\n                    Q[i][j] = Q[i-1][-1]\n                else:\n                    for k in range(rollMax[j]):\n                        Q[i][j]=(Q[i][j]%MAX+(Q[i-k-1][-1]-Q[i-k-1][j])%MAX)%MAX\n                Q[i][-1]=(Q[i][-1]%MAX+Q[i][j]%MAX)%MAX\n        return Q[-1][-1]", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        F = [[0 for i in range(6)] for i in range(n + 1)]\n        sumF = [0 for i in range(n + 1)]\n        for i in range(6):\n            F[1][i] = 1\n        sumF[1] = 6\n        MOD = 10**9 + 7\n        for i in range(2, n + 1):\n            for j in range(6):\n                for p in range(1, rollMax[j] + 1):\n                    if i == p:\n                        F[i][j] = (F[i][j] + 1) % MOD\n                        continue\n                    elif i > p:\n                        F[i][j] = (F[i][j] + sumF[i - p] - F[i - p][j]) % MOD\n                    # for k in range(6):\n                    #     if j == k: continue\n                    #     if i > p:\n                    #         F[i][j] = (F[i][j] + F[i - p][k]) % MOD\n                sumF[i] += F[i][j]\n\n        res = 0\n        for i in range(6):\n            res = (res + F[n][i]) % MOD\n            # print(F[n][i])\n        return round(res)\n        \n        #1(11), 2(11), 3(11), 4(11), 5(11), 6(11) -> 6\n        #1(22), 2(22), 3(22), 4(22), 5(22), 6(22) -> 6\n        #1(33), 2(33), 3(33), 4(33), 5(33), 6(33) -> 6\n        #\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        # dp[i][j] = rolled i times, last face is j\n        # dp[i][0] = rolled i times, any face\n        dp = [[0] * 7 for _ in range(n + 1)]\n        \n        # Base cases\n        for j in range(1, 7):\n            dp[1][j] = 1\n        dp[0][0] = 1\n        dp[1][0] = 6\n        \n        for i in range(2, n + 1):\n            for j in range(1, 7):\n                for k in range(1, min(i, rollMax[j - 1]) + 1):\n                    # (i - k)th roll is not a j,\n                    # so there has been i - (i - k + 1) + 1 = k j's\n                    dp[i][j] = sumMod(dp[i][j], dp[i - k][0] - dp[i - k][j])\n            \n                dp[i][0] = sumMod(dp[i][0], dp[i][j])\n        \n        return dp[n][0]\n    \n    \ndef sumMod(x: int, y: int) -> int:\n    return (x + y) % (10 ** 9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp, tmp, MOD = {}, {}, 10**9+7\n        total, prev = [0] * 6, [0] * 6\n        for k in range(n):\n            for i in range(6):\n                for j in range(1, rollMax[i]+1):\n                    if j > 1:\n                        tmp[(i, j)] = dp[(i, j-1)] if k > 0 else 0\n                    else:\n                        tmp[(i, j)] = (sum(prev) - prev[i]) % MOD if k > 0 else 1\n                    total[i] += tmp[(i, j)]\n            total, prev, dp, tmp = [0]*6, total, tmp, {}\n        return sum(prev) % MOD", "MAX = 10 ** 9 + 7\n\n\nclass Solution:\n    \n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        D = [[0] * 6 for i in range(n + 1)]\n        D[1] = [1] * 6\n        seq_nums = [0] * (n + 1)\n        seq_nums[0], seq_nums[1] = 1, 6\n        for i in range(2, n + 1):\n            for j in range(6):\n                for k in range(1, min(rollMax[j], i) + 1):\n                    D[i][j] = (D[i][j] + seq_nums[i - k] + MAX - D[i - k][j]) % MAX\n                    \n                seq_nums[i] = (seq_nums[i] + D[i][j]) % MAX\n                \n        return seq_nums[-1]", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[] for i in range(6)]\n        for i in range(6):\n            dp[i] = [0] * rollMax[i]\n            dp[i][0] = 1\n        \n        #print(dp)\n        \n        total = 6\n        for i in range(1, n):\n            for j in range(6):\n                tmpSum = sum(dp[j])\n                for k in reversed(range(1, min(rollMax[j], n))):\n                    dp[j][k] = dp[j][k-1]\n                dp[j][0] = total - tmpSum\n            \n            #print(dp)\n            newTotal = 0\n            for j in range(6):\n                newTotal += sum(dp[j])\n            total = newTotal\n        \n        m = pow(10, 9) + 7\n        return total % m", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        dp = [[0] * 7 for _ in range(n + 1)]\n        dp[0][6] = 1\n        for i in range(6):\n            dp[1][i] = 1\n        dp[1][6] = 6\n        \n        for i in range(2, n + 1):\n            total_in_this_pos = 0\n            \n            for j in range(6):\n                total = 0\n                for k in range(max(0, i - rollMax[j]), i):\n                    total += dp[k][6] - dp[k][j]\n                dp[i][j] = total\n                total_in_this_pos += total\n            dp[i][6] = total_in_this_pos\n            \n            # for row in dp:\n            #     print(row)\n        return dp[-1][-1] % MOD\n                    \n                    \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10**9 + 7\n        dp = [[0 for _ in range(7)] for _ in range(n)]\n        for i in range(6):\n            dp[0][i] = 1\n            \n        dp[0][6] = 6\n        for i in range(1, n):\n            sumi = 0\n            for j in range(6):\n                dp[i][j] = dp[i - 1][6]\n                diff = i - rollMax[j]\n                if(diff<0):\n                    sumi = (sumi + dp[i][j])%mod\n                else:\n                    if(diff>=1):\n                        remove = (dp[diff-1][6] - dp[diff-1][j] + mod)%mod\n                        dp[i][j] = (dp[i][j] - remove + mod)%mod\n                    else:\n                        dp[i][j] = (dp[i][j] - 1)%mod\n                    \n                    sumi = (sumi + dp[i][j])%mod\n            dp[i][6] = sumi\n        \n        return dp[n-1][6]", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        to_mod = 10 ** 9 + 7\n        # the index end at, num of consecutive\n        seq_num = [[0 for j in range(rollMax[i] + 1)] for i in range(6)]\n        for i in range(6):\n            if rollMax[i] > 0:\n                seq_num[i][1] = 1\n        for l in range(2, n + 1):\n            new_seq_num = [[0 for i in range(rollMax[j] + 1)] for j in range(6)]\n            seq_sum = [sum(seq_num[i]) % to_mod for i in range(6)]\n            for i in range(6):\n                for j in range(6):\n                    if i != j:\n                        new_seq_num[i][1] += seq_sum[j]\n                    else:\n                        for k in range(2, min(n, rollMax[i]) + 1):\n                            new_seq_num[i][k] = seq_num[i][k - 1]       \n            seq_num = new_seq_num\n        result = 0\n        for i in range(6):\n            result += sum(seq_num[i])\n            result = result % to_mod\n        return result\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * 6 for _ in range(n)]\n        prev = defaultdict(int)\n        MOD = 10**9+7\n\n        for i in range(6):\n            dp[0][i] = 1\n            prev[(i,1)] = 1\n        \n        for i in range(1, n):\n            new = defaultdict(int)\n            for j in range(6):\n                new[(j, 1)] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4] + dp[i-1][5] - dp[i-1][j]\n                dp[i][j] += new[(j, 1)]\n                \n                for k in range(1, rollMax[j]):\n                    new[(j,k+1)] = prev[(j,k)]\n                    dp[i][j] += new[(j,k+1)]\n                dp[i][j] %= MOD\n            prev = new\n            \n        return sum(dp[-1]) % MOD\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10**9 + 7\n        \n        N = n\n        R = len(rollMax)\n        \n        # Set up DP.\n        T = [0] * (N+1)\n        D = [[0] * R for _ in range(N+1)]\n        \n        # Base cases.\n        T[0] = 1\n        T[1] = R\n        D[1] = [1] * R\n        \n        # Compute.\n        for i in range(2, N+1):  # Roll number.\n            for j in range(R):  # Face number.\n                lim = max(i - rollMax[j], 0)\n                for k in range(i-1, lim-1, -1):  # num rolls given last `k` in sequence are `j`\n                    D[i][j] += T[k] - D[k][j]\n            T[i] = sum(D[i])\n            \n        return sum(D[-1]) % mod", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0 for _ in range(rollMax[i])] for i in range(6)]\n        for i in range(6):\n            dp[i][0] = 1\n        for i in range(n - 1):\n            ndp = [[0 for _ in range(rollMax[w])] for w in range(6)]\n            roll_sum = [sum(i) for i in dp]\n            total = sum(roll_sum)\n            for j in range(6):\n                ndp[j][0] = total - roll_sum[j]\n                for k in range(1, rollMax[j]):\n                    ndp[j][k] += dp[j][k - 1]\n            dp = ndp\n        return sum(sum(i) for i in dp) % (10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0] * 6 for _ in range(n+1)]\n        dp[1] = [1] * 6\n        for i in range(2, n+1):\n            for j in range(6):\n                dp[i][j] = sum(dp[i-1][j] for j in range(6))\n                if i == rollMax[j]+1:\n                    dp[i][j] -= 1\n                elif i > rollMax[j]+1:\n                    dp[i][j] -= sum(dp[i-rollMax[j]-1][k] for k in range(6) if k != j)\n        return sum(dp[-1]) % (10**9+7)\n", "from collections import defaultdict\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        if n == 1:\n            return 6\n        cache = {i: defaultdict(int) for i in range(6)}\n        cache_new = {i: defaultdict(int) for i in range(6)}\n        MOD = 10 ** 9 + 7\n        \n        # initialize\n        for i in range(6):\n            cache[i][1] = 1\n        \n        for i in range(2, n+1):\n            for next_dice in range(6):\n                # dice occ 1\n                for prev_dice in range(6):\n                    if prev_dice != next_dice:\n                        cache_new[next_dice][1] += sum(cache[prev_dice].values())\n                cache_new[next_dice][1] %= MOD\n                \n                # dice occ more\n                for occ in range(2, rollMax[next_dice]+1):\n                    cache_new[next_dice][occ] = cache[next_dice][occ-1]\n            cache = cache_new\n            cache_new = {i: defaultdict(int) for i in range(6)}\n            \n        res = 0\n        for i in range(6):\n            res += sum(cache[i].values())\n        return res % MOD", "# Refer discuss\n# https://leetcode.com/problems/dice-roll-simulation/discuss/404840/Short-Python-DP-with-detailed-image-explanation\nclass Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        # [n + 1][faces + 1] dimensional dp array\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        # initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n            # iterate through each column (face)\n            for j in range(faces):\n                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n            # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        mod = 10**9 + 7\n        dp = [[0 for _ in range(7)] for _ in range(n)]\n        for i in range(6):\n            dp[0][i] = 1\n            \n        dp[0][6] = 6\n        for i in range(1, n):\n            sumi = 0\n            for j in range(6):\n                diff = i - rollMax[j]\n                if(diff<0):\n                    dp[i][j] = dp[i - 1][6]\n                    sumi = (sumi + dp[i][j])%mod\n                else:\n                    if(diff>=1):\n                        remove = (dp[diff-1][6] - dp[diff-1][j] + mod)%mod\n                        dp[i][j] = (dp[i - 1][6] - remove + mod)%mod\n                    else:\n                        dp[i][j] = (dp[i - 1][6] - 1)%mod\n                    \n                    sumi = (sumi + dp[i][j])%mod\n            dp[i][6] = sumi\n        \n        return dp[n-1][6]", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        \n        d = [[0] * (faces + 1) for _ in range(n+1)]\n        \n        d[0][faces] = 1\n        \n        for i in range(faces):\n            d[1][i] = 1\n            \n        d[1][faces] = sum(d[1])\n        \n        for i in range(2, n + 1):\n            for j in range(faces):\n                for k in range(1, rollMax[j] + 1):  \n                    if i - k < 0:\n                        break\n                        \n                    d[i][j] += d[i-k][faces] - d[i-k][j]\n            d[i][faces] = sum(d[i])\n            \n        #for i in range(n+1):\n        #    print(d[i])\n                    \n        return d[n][faces] % (10**9+7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0]*7 for x in range(n+1)]\n        dp[0][-1] = 1\n        for x in range(6):\n            dp[1][x] = 1\n        dp[1][-1] = 6\n        \n        for i in range(2, n+1):\n            for j in range(6):\n                for k in range(1, rollMax[j] + 1):\n                    if i-k < 0:\n                        break\n                    dp[i][j] += dp[i-k][-1] - dp[i-k][j]\n            dp[i][-1] = sum(dp[i])\n        return dp[-1][-1] %1000000007\n                    \n            \n            \n            \n            \n            \n            \n            \n            \n            \n    \n    \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        L = len(rollMax)\n        N = n\n        dp = [ [0]*(L+1) for _ in range(N+1) ]      # dp[roll][index]\n        \n        dp[0][L] = 1\n        for i in range(L):\n            dp[1][i] = 1\n        dp[1][L] = L\n        \n        # roll a dice\n        for i in range(2, N+1):\n            # for each faces\n            for j in range(L):\n                for k in range(1, rollMax[j]+1):\n                    if i-k < 0:\n                        break;\n                    dp[i][j] += dp[i-k][L] - dp[i-k][j]\n            # sum all rows\n            dp[i][L] = sum(dp[i][:L])\n            \n        return dp[N][L] % (10**9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n#         self.rollMax = tuple(rollMax)\n        \n#         @lru_cache(None)\n#         def helper(n, ban):\n#             times = 0\n#             if n == 1:\n#                 for t in ban:\n#                     if t > 0:\n#                         times += 1\n#                 return times\n\n#             for i, t in enumerate(ban):\n#                 if t > 0:\n#                     cur = tuple()\n#                     for j in range(len(ban)):\n#                         if i == j:\n#                             cur += (ban[j]-1,)\n#                         else:\n#                             cur += (self.rollMax[j], )\n#                     times += helper(n-1, cur)\n\n#             return times % (10**9 + 7)\n        \n#         return helper(n, tuple(rollMax))\n\n        faces = len(rollMax)\n        # [n + 1][faces + 1] dimensional dp array\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        # initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n            # iterate through each column (face)\n            for j in range(faces):\n                # at each [i, j], trying to go up (decrease i) \n                # and collect all the sum of previous state\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n            # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        '''\n        for j = 0, 1, ..., faces - 1\n        dp[i][j] means how many combinations it could be that at i-th rolling and the last face is j\n        for j = faces\n        dp[i][j] means how many combinations in total with i rollings\n        \n        '''\n        faces = len(rollMax)\n        # [n+1][faces+1] dimensional dp array\n        dp = [[0 for _ in range(faces+1)] for _ in range(n+1)]\n        \n        #initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n+1):\n            # iterate thru each face\n            for j in range(faces):\n                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state\n                for k in range(1, rollMax[j]+1):\n                    if i-k < 0:\n                        break\n                    # give me all the combinations as long as the last face is not j\n                    dp[i][j] += dp[i-k][faces] - dp[i-k][j]\n            dp[i][faces] = sum(dp[i])\n        return dp[n][faces] % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        dp[0][faces] = 1\n        for j in range(faces):\n            dp[1][j] = 1 if rollMax[j] >= 1 else 0\n\n        dp[1][faces] = sum(dp[1][j] for j in range(faces))\n        for i in range(2, n + 1):\n            for j in range(faces):\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        dp = [[0] * (faces + 1) for _ in range(n + 1)]\n        dp[0][faces] = 1\n        for j in range(faces):\n            dp[1][j] = 1\n        dp[1][faces] = faces\n        for i in range(2, n+1):\n            for j in range(faces):\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0:\n                        break\n                    dp[i][j] += dp[i-k][faces] - dp[i-k][j]\n            dp[i][faces] = sum(dp[i])\n        return dp[n][faces] % (10**9 + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        m = len(rollMax)\n        dp = [[0 for j in range(m+1)] for i in range(n+1)]\n        dp[0][m] = 1\n        for j in range(m):\n            dp[1][j] = 1\n        dp[1][m] = m\n        for i in range(2, n+1):\n            for j in range(m):\n                for k in range(1, rollMax[j]+1):\n                    if i-k < 0:\n                        break\n                    dp[i][j] += dp[i-k][m] - dp[i-k][j]\n            dp[i][m] = sum(dp[i])\n        return dp[n][m]%(10**9+7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        faces = len(rollMax)\n        dp = [[0] *(faces + 1) for _ in range(n+1)] \n        \n        dp[0][faces] = 1\n        \n        for j in range(faces):\n            dp[1][j] = 1\n        \n        dp[1][faces] = faces\n        \n        for i in range(2, n+1):\n            for j in range(faces):\n                k = 1\n                while k <= i and k <= rollMax[j]:\n                    dp[i][j] += dp[i-k][faces] - dp[i-k][j]\n                    k += 1\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007\n        \n        \n                \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        numFaces = len(rollMax)\n        dp = [[0 for i in range(numFaces + 1)] for j in range(n + 1)]\n        dp[0][numFaces] = 1\n        for i in range(numFaces):\n            dp[1][i] = 1\n        dp[1][numFaces] = numFaces\n        for i in range(2, n + 1):\n            for j in range(numFaces):\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0: \n                        break\n                    dp[i][j] += dp[i - k][numFaces] - dp[i - k][j]\n            dp[i][numFaces] = sum(dp[i])\n        return dp[n][numFaces] % 1000000007\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0]*7 for i in range(n+1)]\n        dp[0][6]=1\n        for i in range(6):\n            dp[1][i]=1\n        dp[1][6]=6\n        \n        for i in range(2,n+1):\n            for j in range(6):\n                for k in range(1,rollMax[j]+1):\n                    if i-k<0:\n                        break\n                    dp[i][j]+=dp[i-k][6]-dp[i-k][j]\n            dp[i][6] = sum(dp[i])\n        return dp[-1][-1]%(10**9+7)\n                \n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        dp = [[0]*7 for _ in range(n+1)]\n        dp[0][6] = 1\n        for i in range(6):\n            dp[1][i] = 1\n        dp[1][6] = 6\n        for i in range(2,n+1):\n            for roll in range(6):\n                for j in range(1,rollMax[roll]+1):\n                    if i - j < 0: break\n                    dp[i][roll] += dp[i-j][6] - dp[i-j][roll]\n                dp[i][6] += dp[i][roll]\n        return dp[n][6] % (int(1e9) + 7)\n", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        \n        dp = [[0 for _ in range(len(rollMax) + 1)] for _ in range(n + 1)]\n        \n        dp[0][-1] = 1\n        dp[1] = [1] * len(rollMax) + [len(rollMax)]\n        for i in range(2, n + 1):\n            for j in range(len(rollMax)):\n                for k in range(1, rollMax[j] + 1):\n                    if i - k < 0: break\n                    dp[i][j] += dp[i-k][-1] - dp[i-k][j]\n            dp[i][-1] = sum(dp[i])\n        return dp[-1][-1]% 1000000007", "class Solution:\n    def dieSimulator(self, n0, rollMax):\n        nfaces = len(rollMax)\n        lst = [[0] * (nfaces + 1) for _ in range(n0 + 1)]\n        lst[0][-1] = 1\n        for n in range(1, n0 + 1):\n            for face in range(nfaces):\n                for i in range(n, -1, -1):\n                    if n - rollMax[face] > i:\n                        break\n                    lst[n][face] += lst[i][-1] - lst[i][face]\n            lst[n][-1] = sum(lst[n][:-1])\n        return lst[-1][-1] % (10**9 + 7)", "class Solution:\n    def dieSimulator(self, n: int, rollMax: List[int]) -> int:\n        \n        faces = len(rollMax)\n        # [n + 1][faces + 1] dimensional dp array\n        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]\n        \n        # initialization\n        # roll 0 times, the total combination is 1\n        dp[0][faces] = 1\n        # roll 1 times, the combinations that end at face j is 1\n        for j in range(faces):\n            dp[1][j] = 1\n        # roll 1 times, the total combination is faces = 6\n        dp[1][faces] = faces\n        \n        # then roll dices from 2 times, until n times\n        for i in range(2, n + 1):\n            # iterate through each column (face)\n            for j in range(faces):\n                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state\n                k = 1\n                while i - k >= 0 and k <= rollMax[j]:\n                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]\n                    k+=1\n            # update total sum of this row\n            dp[i][faces] = sum(dp[i])\n        \n        return dp[n][faces] % 1000000007\n        \n        \n                \n"]