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:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        a,b,m=[deque([0]*x) for x in rollMax],[1]*6,1000000007
        for x in a: x[-1]=1
        for _ in range(n-1):
            s=sum(b)%m
            for i,x in enumerate(a):
                x.append((s-b[i])%m)
                b[i]=(b[i]+x[-1]-x.popleft())%m
        return sum(b)%m

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MODULO = 10**9 + 7
        
        n_num = len(rollMax)
        
        dp = [[0] * (n_num+1) for _ in range(n+1)]
        dp[0][-1] = 1
        
        dp[1] = [1 for _ in range(n_num+1)]
        dp[1][-1] = n_num
        
        for i in range(2, n+1):
            dp[i] = [(dp[i-1][-1])] * (n_num+1)
            for j in range(n_num):
                k = i - rollMax[j]
                if k > 0:
                    dp[i][j] -= (dp[k-1][-1] - dp[k-1][j])
                dp[i][j] = dp[i][j] % MODULO
            dp[i][-1] = sum(dp[i][:-1]) % MODULO
        
        return dp[-1][-1]



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

        dp = [[0 for _ in range(7)] for i in range(n+1)]
        kMod = 1e9 + 7

        for i in range(1, 7):
            dp[1][i] = 1

        # steps
        for i in range(2, n+1):

            # current value
            for j in range(1, 7):

                k = i-rollMax[j-1]

                # all the posibilities included invalid ones
                dp[i][j] = sum(dp[i-1])

                # take off invalid posibilities
                invalid = max(0, k) if k <= 1 else (sum(dp[k-1])-dp[k-1][j])
                dp[i][j] = ((dp[i][j]-invalid) % kMod+kMod) % kMod

        return int(sum(dp[-1]) % (kMod))



class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        dp = [[0 for _ in range(len(rollMax))] for _ in range(n + 1)]
        sums_dict = {}
        sums_dict[0] = 1
        for j in range(len(rollMax)):
            dp[1][j] = 1
        
        for i in range(2, n + 1):
            sums_dict[i - 1] = sum(dp[i - 1])
            for j in range(len(rollMax)):
                steps = rollMax[j] # number of steps we can go upwards
                k = 1
                ans = 0
                while k <= min(steps, i):
                    row_sum = sums_dict[i - k]
                    ans += row_sum - dp[i - k][j]
                    k += 1
                dp[i][j] = ans
        
        return sum(dp[n]) % (10**9 + 7)
                


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod=10**9+7
        dp=[[1]*6 for i in range(n)]
        for i in range(1,n):
            for j in range(6):
                dp[i][j]=sum([dp[i-1][k] for k in range(6)])
                if i==rollMax[j]:
                    dp[i][j]-=1
                if i>rollMax[j]:
                    dp[i][j]-=sum([dp[i-rollMax[j]-1][k] for k in range(6) if k!=j])
        return sum(dp[-1])%mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = pow(10, 9) + 7
        dp = [[1] + [0 for _ in range(14)] for _ in range(6)]
        
        for _ in range(n - 1):
            dp1 = [[0 for _ in range(15)] for _ in range(6)]
            sums = [sum(s) for s in dp]
            for num in range(6):
                dp1[num][0] = sum(sums[0:num]) + sum(sums[num + 1:])
                for x in range(1, 15):
                    if x > rollMax[num] - 1: break
                    dp1[num][x] = dp[num][x - 1]
            
            dp = dp1
            
        return sum([sum(l) for l in dp]) % mod

from collections import defaultdict

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0]*7 for _ in range(n+1)]
        prev = defaultdict(int)
        
        for i in range(1,7):
            dp[1][i] = 1
            prev[(i,1)] = 1
        
        for i in range(2, n+1):
            new = defaultdict(int)
            for j in range(1, 7):
                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]
                dp[i][j] += new[(j, 1)]
                
                max_len = min(15, rollMax[j-1])
                for k in range(1, max_len):
                    new[(j, k+1)] = prev[(j, k)]
                    dp[i][j] += new[(j, k+1)]
            prev = new
        
        
        count = 0
        for i in range(1,7):
            count += dp[n][i]
        return count%1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        # [n + 1][faces + 1] dimensional dp array
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
        # initialization
        # roll 0 times, the total combination is 1
        dp[0][faces] = 1
        # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
        # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
        
        # then roll dices from 2 times, until n times
        for i in range(2, n + 1):
            # iterate through each column (face)
            for j in range(faces):
                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]
            # update total sum of this row
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007

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

        results = [[0 for _ in range(7)] for _ in range(n+1)]
        results[0][6] = 1

        for i in range(1, n+1):
            for j in range(6):
                suma = 0
                for roll_max in range(min(rollMax[j], i)):
                    suma += results[i-1-roll_max][6] - results[i-1-roll_max][j]
                results[i][j] = suma
            results[i][6] = sum(results[i])

        return results[n][6] % (10**9 + 7)

class Solution:
#     https://leetcode.com/problems/dice-roll-simulation/discuss/404840/Short-Python-DP-with-detailed-image-explanation
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        record = [[0] * (faces+1) for _ in range(n+1)]
        record[0][faces] = 1
        for i in range(faces):
            record[1][i] = 1
        record[1][faces] = 6
        for i in range(2,n+1):
            for j in range(faces):
                for k in range(1,rollMax[j]+1):
                    if i - k < 0:
                        break
                    record[i][j] += record[i-k][faces] - record[i-k][j]
            record[i][faces] = sum(record[i])
        return record[-1][faces]%(10**9+7)  
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp= [[0 for _ in range(7)] for _ in range(n+1)]
        dp[0][6]=1
        for r in range(1,n+1):
            for f in range(6):
                k = 1
                while(k<=rollMax[f] and r-k>=0):
                    dp[r][f] += dp[r-k][6]-dp[r-k][f] 
                    k +=1
                
            dp[r][6]=sum(dp[r][:6])
        return (dp[-1][-1])%(10**9+7)



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

        # dp[at nth roll][count of current number (1~6)]
        dp = [[[0 for _ in range(max(rollMax) + 1)]
               for _ in range(7)] for _ in range(n + 1)]
        kMod = 1e9 + 7
        for i in range(1, 7):
            dp[1][i][1] = 1

        for i in range(2, n + 1):
            for j in range(1, 7):
                for l in range(1, 7):
                    if l != j:
                        dp[i][j][1] += sum(dp[i - 1][l]) % kMod
                    else:
                        for k in range(1, rollMax[j - 1] + 1):
                            dp[i][j][k] += dp[i - 1][j][k - 1] % kMod

        temp = sum([(sum(i) % kMod) for i in dp[-1]])

        return int(temp % kMod)

    def dieSimulator_temp(self, n: int, rollMax: List[int]) -> int:

        dp = [[0 for _ in range(7)] for i in range(n+1)]
        kMod = 1e9 + 7

        for i in range(1, 7):
            dp[1][i] = 1

        # steps
        for i in range(2, n+1):

            # current value
            for j in range(1, 7):

                k = i-rollMax[j-1]

                # all the posibilities included invalid ones
                dp[i][j] = sum(dp[i-1])

                # take off invalid posibilities
                invalid = max(0, k) if k <= 1 else (sum(dp[k-1])-dp[k-1][j])
                dp[i][j] = ((dp[i][j]-invalid) % kMod+kMod) % kMod

        return int(sum(dp[-1]) % (kMod))



class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
    
    # initialization
    # roll 0 times, the total combination is 1
        dp[0][faces] = 1
    # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
    # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
    
    # then roll dices from 2 times, until n times
        for i in range(2, n + 1):
        # iterate through each column (face)
            for j in range(faces):
                dp[i][j] = dp[i - 1][-1]
                if i-1-rollMax[j] >= 0:
                    dp[i][j] -= (dp[i-1-rollMax[j]][-1] - dp[i-1-rollMax[j]][j])
        # update total sum of this row
            dp[i][faces] = sum(dp[i])
    
        return dp[n][faces]%1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        table = [[0 for _ in range(len(rollMax) + 1)] for _ in range(n + 1)]
        table[0][len(rollMax)] = 1
        
        for j in range(len(rollMax)):
            table[1][j] = 1
            
        table[1][len(rollMax)] = 6
        
        for i in range(2, n + 1):
            for j in range(len(rollMax)):
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    table[i][j] += table[i - k][len(rollMax)] - table[i - k][j] 
            table[i][len(rollMax)] = sum(table[i])  
        return table[-1][-1] % (10**9 + 7)


class Solution:
#     https://leetcode.com/problems/dice-roll-simulation/discuss/404840/Short-Python-DP-with-detailed-image-explanation
    # Use a 2D dimensional board to record the possible number of times of one face at one throw
    # The current times = previous K times (i-k<0) (each time, the total number of all faces - this number)
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        record = [[0] * (faces+1) for _ in range(n+1)]
        record[0][faces] = 1
        for i in range(faces):
            record[1][i] = 1
        record[1][faces] = 6
        for i in range(2,n+1):
            for j in range(faces):
                for k in range(1,rollMax[j]+1):
                    if i - k < 0:
                        break
                    record[i][j] += record[i-k][faces] - record[i-k][j]
            record[i][faces] = sum(record[i])
        return record[-1][faces]%(10**9+7)  
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        # [n + 1][faces + 1] dimensional dp array
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
        # initialization
        # roll 0 times, the total combination is 1
        dp[0][faces] = 1
        # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
        # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
        
        # then roll dices from 2 times, until n times
        for i in range(2, n + 1):
            # iterate through each column (face)
            for j in range(6):
                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]
            # update total sum of this row
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007




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

        # dp[at nth roll][count of current number (1~6)]
        dp = [[[0 for _ in range(max(rollMax) + 1)]
               for _ in range(7)] for _ in range(n + 1)]
        kMod = 1e9 + 7
        for i in range(1, 7):
            dp[1][i][1] = 1

        for i in range(2, n + 1):
            for j in range(1, 7):
                for l in range(1, 7):
                    if l != j:
                        dp[i][j][1] += sum(dp[i - 1][l]) % kMod
                    else:
                        for k in range(1, rollMax[j - 1] + 1):
                            dp[i][j][k] += dp[i - 1][j][k - 1] % kMod

        temp = sum([(sum(i) % kMod) for i in dp[-1]])

        return int(temp % kMod)

    def dieSimulator_temp(self, n: int, rollMax: List[int]) -> int:

        dp = [[0 for _ in range(7)] for i in range(n+1)]
        kMod = 1e9 + 7
        
        for i in range(1, 7):
            dp[1][i] = 1

        # steps
        for i in range(2, n+1):

            # current value
            for j in range(1, 7):

                k = i-rollMax[j-1]

                # all the posibilities included invalid ones
                dp[i][j] = sum(dp[i-1])

                # take off invalid posibilities
                invalid = max(0, k) if k <= 1 else (sum(dp[k-1])-dp[k-1][j])
                dp[i][j] = ((dp[i][j]-invalid) % kMod+kMod) % kMod

        return int(sum(dp[-1]) % (kMod))



class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        faces = len(rollMax)
        # [n + 1][faces + 1] dimensional dp array
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
        # initialization
        # roll 0 times, the total combination is 1
        dp[0][faces] = 1
        # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
        # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
        
        # then roll dices from 2 times, until n times
        for i in range(2, n + 1):
            # iterate through each column (face)
            for j in range(faces):
                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]
            # update total sum of this row
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007
        
        
                


  
        
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        # [n + 1][faces + 1] dimensional dp array
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
        # initialization
        # roll 0 times, the total combination is 1
        dp[0][faces] = 1
        # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
        # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
        
        # then roll dices from 2 times, until n times
        for i in range(2, n + 1):
            # iterate through each column (face)
            for j in range(faces):
                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]
            # update total sum of this row
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0 for i in range(7)] for j in range(n + 1)]
        dp[0][6] = 1
        for j in range(6):
            dp[1][j] = 1
        dp[1][6] = 6
        
        for i in range(2, n + 1):
            for j in range(6):
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    dp[i][j] += dp[i - k][6] - dp[i - k][j]
            dp[i][6] = sum(dp[i])
        
        return dp[n][6] % 1000000007


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        faces = len(rollMax)
        # [n + 1][faces + 1] dimensional dp array
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
        # initialization
        # roll 0 times, the total combination is 1
        dp[0][faces] = 1
        # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
        # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
        
        # then roll dices from 2 times, until n times
        for i in range(2, n + 1):
            # iterate through each column (face)
            for j in range(faces):
                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state
                k = 1
                while i >= k and k <= rollMax[j]:
                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]
                    k+=1
            # update total sum of this row
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007
        
        
                


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dp[i][j][k]
        dp = [[[0 for _ in range(16)] for _ in range(6)] for _ in range(n + 1)]
        
        # 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.
        
        for i in range(0, 6):
            dp[1][i][1] = 1
        
        for i in range(2, n + 1):
            for j in range(0, 6):
                for k in range(1, rollMax[j] + 1):
                    if k > i:
                        continue
                    
                    if k == 1:
                        # The previous roll must have been different.
                        for l in range(0, 6):
                            if l == j:
                                continue
                            s = int(sum(dp[i - 1][l]) % (1e9 + 7))
                            dp[i][j][k] += s
                    else:
                        # The previous roll must have been the same.
                        dp[i][j][k] += dp[i - 1][j][k - 1]
                        
                    
        ans = 0
        for arr in dp[n]:
            ans = ans + sum(arr)
        return int(ans % (1e9 + 7))

#[] DP(bottom-up)
#O(6N * 6T): T: upperbound of rollMax

#f(i, d): number of combinations of res[0~i] if the last number is d
#f(i, ?) = 1 if i == 0
#                 |------------| <= rollMax[d]
#               d'd d d ... d [d]
#               ? d'd d ... d [d]
#               ? ? d'd ... d [d]
#               ? ? ? d'... d [d]
#               ? ? ? ? ... d'[d]
#f(i, d) = sum{ f(j, d') for j in i-rollMax[d] ~ i-1 for d' in 0~5
#               if i-rollMax[d] >= 0 and d' != d }
#          sum{ f(i-1, d') for any d' if i < rollMax[d]} < no limit
MOD = 1000000007
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * 6 for _ in range(n)]
        for d in range(6):
            dp[0][d] = 1
        for i in range(1, n):
            for d in range(6):
                if i < rollMax[d]: #no constraint
                    dp[i][d] = sum(dp[i-1][x] for x in range(6)) % MOD
                else:
                    dp[i][d] = sum(dp[j][x] for j in range(i-rollMax[d], i) for x in range(6) if x != d) % MOD
        return sum(dp[n-1][d] for d in range(6)) % MOD

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        memo = [[0] * 7 for _ in range(n + 1)]
        for j in range(6):
            memo[1][j] = 1
            memo[1][-1] += memo[1][j]
        for i in range(2, n + 1):
            for j in range(6):
                memo[i][j] = memo[i - 1][-1]
                k = i - rollMax[j]
                if k == 1: memo[i][j] -= 1
                elif k > 1: memo[i][j] -= (memo[k - 1][-1] - memo[k - 1][j])
                memo[i][-1] += memo[i][j]
        return memo[n][6] % int(1e9 + 7)

# https://leetcode.com/problems/dice-roll-simulation/discuss/404840/Short-Python-DP-with-detailed-image-explanation
# 解説見ればわかるけど、難しい


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        dp[0][faces] = 1
        for j in range(faces):
            dp[1][j] = 1
        dp[1][faces] = faces
        
        for i in range(2, n+1):
            for j in range(faces):
                for k in range(1, rollMax[j]+1):
                    if i - k < 0:
                        break
                    dp[i][j] += dp[i-k][faces] - dp[i-k][j]
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % (10**9+7)
        
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        k={}
        mod=10**9+7
        for i in range(6):
            k[i]=[0 for i in range(rollMax[i])]
            if k[i]:
                k[i][-1]=1
        for i in range(n):
            su=0
            temp_su=[0 for j in range(6)]
            for j in range(6):
                val=sum(k[j])
                su+=val
                temp_su[j]=val
            for j in range(6):
                temp=[x for x in k[j]]
                for x in range(rollMax[j]-1):
                    temp[x]=k[j][x+1]%mod
                temp[-1]=su-temp_su[j]%mod
                k[j]=temp
        return su%mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        
        '''
        https://leetcode.com/problems/dice-roll-simulation/discuss/403756/Java-Share-my-DP-solution
        
        num[i,j] = num sequences with i rolls that ends with j
        
        num[i,j] = sum_{k≠j} (num[i-1,k]) + num[i-1,j] - num[i-rollMax[i],j]
        '''
        
        num = [[1]*6+[6] for i in range(16)]  # rollMax[i] <= 15
        pointer = 1
        
        def idxLast(i):
            return (pointer - i) % 16
        
        for k in range(2,n+1):
            
            for j in range(6):
                
                if rollMax[j] >= k:
                    num[idxLast(0)][j] = num[idxLast(1)][-1]
                
                else:
                    num[idxLast(0)][j] = 0
                    for i in range(1, rollMax[j]+1):
                        num[idxLast(0)][j] = (num[idxLast(0)][j] + num[idxLast(i)][-1] - num[idxLast(i)][j]) % int(1E9 + 7)
            
            num[idxLast(0)][-1] = sum(num[idxLast(0)][:6]) % int(1E9 + 7)
            
            pointer += 1
        
        # print(num)
        
        return num[idxLast(1)][-1] % int(1E9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        # [n + 1][faces + 1] dimensional dp array
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
        # initialization
        # roll 0 times, the total combination is 1
        dp[0][faces] = 1
        # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
        # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
        
        # then roll dices from 2 times, until n times
        for i in range(2, n + 1):
            # iterate through each column (face)
            for j in range(faces):
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0: break 
                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]
            # update total sum of this row
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        face = len(rollMax)
        
        dp = [[0 for i in range(face + 1)] for j in range(n + 1)]

        # 0 roll
        dp[0][face] = 1
        # 1 roll
        for f in range(face):
            dp[1][f] = 1
        dp[1][face] = 6
        # 2 roll and more

        for i in range(2, n + 1):
            for j in range(face):
                for k in range(1, rollMax[j] + 1):
                    if (i - k) < 0:
                        break
                    dp[i][j] += dp[i - k][face] - dp[i - k][j]
            dp[i][face] = sum(dp[i])
        
        return dp[n][face]%1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0 for _ in range(7)] for _ in range(n+1)]
        dp[0][6] = 1
        for j in range(6):
            dp[1][j] = 1
        dp[1][6] = sum(dp[1])
        for i in range(2, n+1):
            for j in range(6):
                dp[i][j] = dp[i-1][6]
                if i - rollMax[j] - 1 >= 0:
                    dp[i][j] -= dp[i - rollMax[j] - 1][-1] - dp[i - rollMax[j] - 1][j]
            dp[i][-1] = sum(dp[i])
        return dp[n][6] % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        dp[0][faces] = 1
        for j in range(faces):
            dp[1][j] = 1
        dp[1][faces] = faces
        for i in range(2, n + 1):
            for j in range(faces):
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]
            dp[i][faces] = sum(dp[i])
        return dp[n][faces] % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[] for i in range(6)]
        new_dp = [[] for i in range(6)]
        for i in range(6):
            dp[i].append(1)
            for j in range(1, rollMax[i]):
                dp[i].append(0)
            new_dp[i] = [0 for i in range(rollMax[i])] 
        for r in range(1, n):    
            for i in range(6):
                new_dp[i][0] = sum([sum(dp[j]) if j != i else 0 for j in range(6)])
                for j in range(1, rollMax[i]):
                    new_dp[i][j] = dp[i][j-1]
            dp, new_dp = new_dp, dp
        return sum([sum(x) for x in dp]) % (10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * 6 + [1] for i in range(n + 1)]
        dp[1] = [1] * 6 + [6] 
        #print(dp)
        for i in range(2, n+1):
            for j in range(6):
                for k in range(1, rollMax[j]+1):
                    if i - k < 0: break
                    dp[i][j] += dp[i-k][6] - dp[i-k][j]
            #print(dp[i])
            dp[i][6] = sum(dp[i][:-1])
        #print(dp)
        return dp[-1][-1] % (10**9+7)

        



class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * 6 + [1] for i in range(n + 1)]
        dp[1] = [1] * 6 + [6] 
        for i in range(2, n+1):
            for j in range(6):
                for k in range(1, rollMax[j]+1):
                    if i - k < 0: break
                    dp[i][j] += dp[i-k][6] - dp[i-k][j]
            dp[i][6] = sum(dp[i][:-1])
        return dp[-1][-1] % (10**9+7)

        



class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        if n == 0:
            return 0
        hist = [[0 for _ in range(rollMax[i])] for i in range(6)]
        for i in range(6):
            hist[i][0] = 1
        
        for i in range(n-1):
            new = [[0 for _ in range(rollMax[i])] for i in range(6)]
            for j in range(6):
                s = sum(sum(e) for idx, e in enumerate(hist) if idx != j)
                new[j][0] = s
                for rep in range(1, rollMax[j]):
                    new[j][rep] = hist[j][rep-1]
            hist = new
        
        return sum(sum(e) for e in hist) % (1000000007)

# from copy import deepcopy
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0 for _ in range(i)] for i in rollMax]
        
        def sum_dp(j = -1):
            return sum(sum(x) for index, x in enumerate(dp) if index != j)
        
        for i in range(6):
            dp[i][0] = 1
        
        # print(dp)
        for i in range(n-1):
            dp2 = [[0 for _ in range(i)] for i in rollMax]
            for j in range(6):
                max_len = len(dp[j])
                for k in range(max_len-1, 0, -1):
                    dp2[j][k] = dp[j][k-1]
                dp2[j][0] = sum_dp(j)
            dp = dp2
        
        # print(dp)
        return sum_dp() % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        dp =collections.deque([[0] * 6 for i in range(max(rollMax))])
        dp[0] = [1] * 6
        for i in range(2,  n + 1):
            dp2 = [0]  * 6
            for j in range(6):
                if rollMax[j] >= i:
                    dp2[j] = 1
                for k in range(min(rollMax[j], i)):
                    for d in range(6):
                        if d == j:
                            continue
                        dp2[j] = (dp2[j] + dp[k][d]) % MOD
            dp.pop()
            dp.appendleft(dp2)
        return sum(dp[0]) % MOD


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dynamic programming
        # dp[i][j]: num of seqs for i + 1 rolls that ends at face j + 1
        dp = [[0 for c in range(6)] for r in range(n)]
        # initialize
        for c in range(6):
            dp[0][c] = 1
        # fill in dp by rows
        for r in range(1, n):
            for c in range(6):
                if r < rollMax[c]:
                    dp[r][c] = sum(dp[r-1])
                else:
                    for prev in range(r - rollMax[c], r):
                        dp[r][c] += sum(dp[prev]) - dp[prev][c]
        return sum(dp[-1]) % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        dp =collections.deque([[0] * 7 for i in range(max(rollMax))])
        dp[0] = [1] * 7
        for i in range(1,  n + 1):
            dp2 = [0]  * 7
            for j in range(7):
                for d in range(6):
                    if d == j:
                        continue
                    for k in range(min(rollMax[d], i)):
                        dp2[j] = (dp2[j] + dp[k][d]) % MOD
            dp.pop()
            dp.appendleft(dp2)
        return dp[0][6]


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
             dp=[[0]*7 for i in range(n+1)]
             dp[0][-1]=1
             for j in range(6):
                dp[1][j]=1
             dp[1][-1]=6
             for i in range(2,n+1):
                  for j in range(6):
                     dp[i][j]=dp[i-1][-1]
                     k=i-rollMax[j]-1
                     if k>=0:
                        dp[i][j]-=(dp[k][-1]-dp[k][j])
                     dp[i][-1]+=dp[i][j]
             return dp[-1][-1]%int(1e9+7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10**9 + 7
        dp = [[0, 1] + [0] * 15 for i in range(6)]
        for _ in range(n - 1):
            dp2 = [[0] * 17 for i in range(6)]
            for i in range(6):
                for k in range(1, rollMax[i] + 1):
                    for j in range(6):
                        if i == j:
                            if k < rollMax[i]:
                                dp2[j][k + 1] += dp[i][k] % mod
                        else:
                            dp2[j][1] += dp[i][k] % mod
            dp = dp2
        return sum(sum(row) for row in dp) % mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        dp =collections.deque([[0] * 7 for i in range(max(rollMax))])
        dp[0] = [1] * 7
        for i in range(1,  n + 1):
            dp2 = [0]  * 7
            for j in range(7):
                for d in range(6):
                    if d == j:
                        continue
                    for k in range(min(rollMax[d], i)):
                        dp2[j] = (dp2[j] + dp[k][d]) % MOD
            dp.pop()
            dp.appendleft(dp2)
        # print(dp)
        return dp[0][6] % MOD
#         @lru_cache(None)
#         def roll(j, i):
#             if i == 0:
#                 return 1
#             cnt = 0
#             for d in range(6):
#                 if d != j:
#                     for k in range(min(rollMax[d], i)):
#                         cnt = (cnt + roll(d, i - k - 1)) % MOD
#             return cnt
        
#         return roll(-1, n)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        p = 10**9 + 7
        C = [[[0 for v in range(rollMax[i])] for i in range(6)] for k in range(n)]
        for i in range(6):
            C[0][i][0] = 1
        for k in range(n-1):
            A = {}
            for i in range(6):
                for v in range(rollMax[i]-1):
                    A[(i,v+1)] = C[k][i][v]
                A[(i,0)] = sum([C[k][i1][v] for i1 in range(6) for v in range(rollMax[i1]) if i1!=i])
            for i in range(6):
                for v in range(rollMax[i]):
                    C[k+1][i][v] = A[(i,v)]%p
#        print(C)
        return(sum([sum(row) for row in C[-1]])%p)

class Solution:
    def dieSimulator(self, n, rollMax):
        mod = 10**9 + 7
        dp = [[0, 1] + [0] * 15 for i in range(6)]
        for _ in range(n - 1):
            dp2 = [[0] * 17 for i in range(6)]
            for i in range(6):
                for k in range(1, rollMax[i] + 1):
                    for j in range(6):
                        if i == j:
                            if k < rollMax[i]:
                                dp2[j][k + 1] += dp[i][k] % mod
                        else:
                            dp2[j][1] += dp[i][k] % mod
            dp = dp2
        return sum(sum(row) for row in dp) % mod

class Solution:
    def dieSimulator(self, n, rollMax):
        mod = 10**9 + 7
        dp = [[0, 1] + [0] * 15 for i in range(6)]
        for _ in range(0, n - 1):
            dp2 = [[0] * 17 for i in range(0,6)]
            for i in range(6):
                for k in range(1, rollMax[i] + 1):
                    for j in range(6):
                        if i == j:
                            if k < rollMax[i]:
                                dp2[j][k + 1] += dp[i][k] % mod
                        else:
                            dp2[j][1] += dp[i][k] % mod
            dp = dp2
        return sum(sum(row) for row in dp) % mod


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dp[i][k] means after several rolls, the number of sequence that ends with k times i.
        mod = 10**9 + 7
        dp = [[0, 1] + [0] * 14 for i in range(6)]
        for _ in range(n - 1):
            dp2 = [[0] * 16 for i in range(6)]
            for i in range(6):
                for k in range(1, rollMax[i] + 1):
                    for j in range(6):
                        if i == j:
                            if k < rollMax[i]:
                                dp2[j][k + 1] += dp[i][k] % mod
                        else:
                            dp2[j][1] += dp[i][k] % mod
            dp = dp2
        return sum(sum(row) for row in dp) % mod
        
        
        
        
        # mod = 10**9 + 7
        # dp = [[0, 1] + [0] * 15 for i in range(6)]
        # for _ in range(n - 1):
        #     dp2 = [[0] * 17 for i in range(6)]
        #     for i in range(6):
        #         for k in range(1, rollMax[i] + 1):
        #             for j in range(6):
        #                 if i == j:
        #                     if k < rollMax[i]:
        #                         dp2[j][k + 1] += dp[i][k] % mod
        #                 else:
        #                     dp2[j][1] += dp[i][k] % mod
        #     dp = dp2
        # return sum(sum(row) for row in dp) % mod


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        @lru_cache(None)
        def roll(j, i):
            if i == 0:
                return 1
            if i < 0:
                return 0
            cnt = 0
            for d in range(6):
                if d != j:
                    for k in range(rollMax[d]):
                        cnt = (cnt + roll(d, i - k - 1)) % MOD
            return cnt
        
        return roll(-1, n)

class Solution:
    def dieSimulator(self, n, rollMax):
        mod = 10**9 + 7
        dp = [[0, 1] + [0] * 15 for i in range(6)]
        for _ in range(n - 1):
            dp2 = [[0] * 17 for i in range(6)]
            for i in range(6):
                for k in range(1, rollMax[i] + 1):
                    for j in range(6):
                        if i == j:
                            if k < rollMax[i]:
                                dp2[j][k + 1] += dp[i][k] % mod
                        else:
                            dp2[j][1] += dp[i][k] % mod
            dp = dp2
        return sum(sum(row) for row in dp) % mod
#     def dieSimulator(self, n: int, rollMax: List[int]) -> int:
#         faces = len(rollMax)
#         # [n + 1][faces + 1] dimensional dp array
#         dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
#         # initialization
#         # roll 0 times, the total combination is 1
#         dp[0][faces] = 1
#         # roll 1 times, the combinations that end at face j is 1
#         for j in range(faces):
#             dp[1][j] = 1
#         # roll 1 times, the total combination is faces = 6
#         dp[1][faces] = faces
        
#         # then roll dices from 2 times, until n times
#         for i in range(2, n + 1):
#             # iterate through each column (face)
#             for j in range(faces):
#                 # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state
#                 dp[i][j] = dp[i-1][faces]
#                 if i-1-rollMax[j] >= 0:
#                     dp[i][j] -= (dp[i-1-rollMax[j]][faces] - dp[i-1-rollMax[j]][j])
#             # update total sum of this row
#             dp[i][faces] = sum(dp[i])
        
#         return dp[n][faces] % 1000000007


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        # [n + 1][faces + 1] dimensional dp array
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
        # initialization
        # roll 0 times, the total combination is 1
        dp[0][faces] = 1
        # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
        # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
        
        # then roll dices from 2 times, until n times
        for i in range(2, n + 1):
            # iterate through each column (face)
            for j in range(faces):
                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state
                dp[i][j] = dp[i-1][faces]
                if i-1-rollMax[j] >= 0:
                    dp[i][j] -= (dp[i-1-rollMax[j]][faces] - dp[i-1-rollMax[j]][j])
            # update total sum of this row
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [ [0 for _ in range(7)] for _ in range(n+1) ]
        dp[1] = [0] + [1 for _ in range(1, 7)]
        mod = 10**9+7
        
        for i in range(2, n+1):
            for j in range(1, 7):
                for k in range(1, rollMax[j-1]+1):
                    if i-k > 0:
                        dp[i][j] += sum(dp[i-k]) - dp[i-k][j]
                    if i-k == 0:
                        dp[i][j] += 1
        
        return sum(dp[n])%mod
        


from typing import List
import collections
import heapq
import itertools
import bisect
import copy
import random
import re
import fractions
import math

mod = 10 ** 9 + 7


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

        rollMax = [0] + rollMax
        dp = [[0, 1] + [0] * 15 for _ in range(7)]

        for _ in range(2, n + 1):
            dp2 = [[0] * 17 for _ in range(7)]
            for i in range(1, 7):
                for j in range(1, 7):
                    for k in range(1, rollMax[j] + 1):  # we could extend j no more
                        if i == j:
                            if k < rollMax[i]:
                                dp2[i][k + 1] += dp[i][k] % mod
                        else:
                            dp2[i][1] += dp[j][k] % mod

            dp = dp2

        return sum(map(sum, dp)) % mod


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        @lru_cache(None)
        def roll(i, j):
            if i == 0:
                return 1
            if i < 0:
                return 0
            cnt = 0
            for d in range(6):
                if d != j:
                    for k in range(rollMax[d]):
                        cnt = (cnt + roll(i - k - 1, d)) % MOD
            return cnt
        
        return roll(n, -1)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10**9 + 7
        dp = [[0, 1] + [0] * 15 for _ in range(6)]
        for _ in range(n - 1):
            dp2 = [[0] * 17 for _ in range(6)]
            for i in range(6):
                for k in range(1, rollMax[i] + 1):
                    for j in range(6):
                        if j == i:
                            if k < rollMax[i]:
                                dp2[j][k + 1] += dp[i][k] % mod
                        else:
                            dp2[j][1] += dp[i][k] % mod
            dp = dp2
        return sum(sum(d) for d in dp) % mod
            


from functools import lru_cache

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10**9+7
        @lru_cache
        def roll(i, j):
            # print(i, j)
            if i == 0:
                return 1

            ans = 0
            for dice in range(6):
                if dice == j: 
                    continue
                
                for k in range(1, min(rollMax[dice], i)+1):
                    # print('roll', dice, k, i-k)
                    ans += roll(i-k, dice)
                    ans %= MOD
            return ans % MOD
        
        return roll(n, -1)
                
    
# class Solution:
#     def dieSimulator(self, n: int, rollMax: List[int]) -> int:
#         dp = [[0] * 6 for _ in range(n+1)]
#         dp[1] = [1] * 6
#         # print(dp[1])
        
#         for i in range(2, n+1):
#             for j in range(6):
#                 pi = i - rollMax[j]
#                 if pi < 1:
#                     dp[i][j] = sum(dp[i-1])
#                 elif pi == 1:
#                     dp[i][j] = sum(dp[i - 1]) - 1
#                 elif pi > 1:
#                     dp[i][j] = sum(dp[i - 1]) - sum(dp[pi-1][:j] + dp[pi-1][j + 1:]) 
#                 dp[i][j] = dp[i][j] % (10**9 + 7)
#             # print(dp[i])
#         return sum(dp[-1]) % (10**9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dp[i][k] means after several rolls, the number of sequence that ends with i for k times.
        mod = 10**9 + 7
        dp = [[0, 1] + [0] * 14 for i in range(6)]
        for _ in range(n - 1):
            dp2 = [[0] * 16 for i in range(6)]
            # update the dp table
            for i in range(6):
                for k in range(1, rollMax[i] + 1):
                    # all choices
                    for j in range(6):
                        # if same, only not > max
                        if i == j:
                            if k < rollMax[i]:
                                dp2[j][k + 1] += dp[i][k] % mod
                        # if not, add anyway
                        else:
                            dp2[j][1] += dp[i][k] % mod
            dp = dp2
        return sum(sum(row) for row in dp) % mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        @lru_cache(None)
        def roll(j, i):
            if i == 0:
                return 1
            if i < 0:
                return 0
            cnt = 0
            for d in range(6):
                if d != j:
                    for k in range(min(rollMax[d], i)):
                        cnt = (cnt + roll(d, i - k - 1)) % MOD
            return cnt
        
        return roll(-1, n)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        @lru_cache(None)
        def roll(j, i):
            if i == 0:
                return 1
            cnt = 0
            for d in range(6):
                if d != j:
                    for k in range(min(rollMax[d], i)):
                        cnt = (cnt + roll(d, i - k - 1)) % MOD
            return cnt
        
        return roll(-1, n)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        mod = 10**9 + 7
        dp = [[0, 1] + [0] * 14 for i in range(6)]
        for _ in range(n - 1):
            dp2 = [[0] * 16 for i in range(6)]
            for i in range(6):
                for k in range(1, rollMax[i] + 1):
                    for j in range(6):
                        if i == j:
                            if k < rollMax[i]:
                                dp2[j][k + 1] += dp[i][k] % mod
                        else:
                            dp2[j][1] += dp[i][k] % mod
            dp = dp2
        return sum(sum(row) for row in dp) % mod
    
    
        M, K = 6, 15
        dp = [[[0]*(K + 1) for _ in range(M + 1)] for _ in range(n + 1)]
        
        for i in range(1, M+1):
            dp[1][i][1] = 1
            
        for i in range(2, n+1):           
            for j in range(1, M+1):                  
                for m in range(1, M+1):
                    if m != j:
                        dp[i][j][1] += sum(dp[i-1][m][h] for h in range(1, rollMax[m-1] + 1))

                for k in range(1, K):                  
                    dp[i][j][k+1] += dp[i-1][j][k]   
                
        ans = 0
        for m in range(1, M+1):
            for k in range(1, rollMax[m-1] + 1):
                ans += dp[-1][m][k]
                
        return ans % (10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        mod = 10**9 + 7
        dp = [[0, 1] + [0] * 15 for i in range(6)]
        for _ in range(n - 1):
            dp2 = [[0] * 17 for i in range(6)]
            for i in range(6):
                for k in range(1, rollMax[i] + 1):
                    for j in range(6):
                        if i == j:
                            if k < rollMax[i]:
                                dp2[j][k + 1] += dp[i][k] % mod
                        else:
                            dp2[j][1] += dp[i][k] % mod
            dp = dp2
        return sum(sum(row) for row in dp) % mod
    
    
        M, K = 6, 15
        dp = [[[0]*(K + 1) for _ in range(M + 1)] for _ in range(n + 1)]
        
        for i in range(1, M+1):
            dp[1][i][1] = 1
            
        for i in range(2, n+1):           
            for j in range(1, M+1):                  
                for m in range(1, M+1):
                    if m != j:
                        dp[i][j][1] += sum(dp[i-1][m][h] for h in range(1, rollMax[m-1] + 1))

                for k in range(1, K):                  
                    dp[i][j][k+1] += dp[i-1][j][k]   
                
        ans = 0
        for m in range(1, M+1):
            for k in range(1, rollMax[m-1] + 1):
                ans += dp[-1][m][k]
                
        return ans % (10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        # [n + 1][faces + 1] dimensional dp array
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
        # initialization
        # roll 0 times, the total combination is 1
        dp[0][faces] = 1
        # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
        # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
        
        # then roll dices from 2 times, until n times
        for i in range(2, n + 1):
            # iterate through each column (face)
            for j in range(faces):
                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state
                dp[i][j] = dp[i-1][faces]
                if i-1-rollMax[j] >= 0:
                    dp[i][j] -= (dp[i-1-rollMax[j]][faces] - dp[i-1-rollMax[j]][j])
                # for k in range(1, rollMax[j] + 1):
                #     if i - k < 0:
                #         break
                #     dp[i][j] += dp[i - k][faces] - dp[i - k][j]
            # update total sum of this row
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # 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])
        dp = [[[0]*(max(rollMax)+1) for _ in range(6)] for _ in range(n)]
        mod = 10**9 + 7
        for j in range(6):
            dp[0][j][1] = 1
        for i in range(1,n):
            for j in range(6):
                for k in range(1,min(rollMax[j]+1,i+2)):
                    if k == 1:
                        for prevj in range(6):
                            if prevj != j:
                                dp[i][j][k] += sum(dp[i-1][prevj])
                    else:
                        dp[i][j][k] = dp[i-1][j][k-1] 
        return sum([sum(dp[-1][j]) for j in range(6)]) % mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        F = [[0 for i in range(6)] for i in range(n + 1)]
        sumF = [0 for i in range(n + 1)]
        for i in range(6):
            F[1][i] = 1
        sumF[0] = 6
        MOD = 10**9 + 7
        for i in range(2, n + 1):
            for j in range(6):
                for p in range(1, rollMax[j] + 1):
                    if i == p:
                        F[i][j] = (F[i][j] + 1) % MOD
                        continue
                    for k in range(6):
                        if j == k: continue
                        if i > p:
                            F[i][j] = (F[i][j] + F[i - p][k]) % MOD

        res = 0
        for i in range(6):
            res = (res + F[n][i]) % MOD
            # print(F[n][i])
        return round(res)
        
        #1(11), 2(11), 3(11), 4(11), 5(11), 6(11) -> 6
        #1(22), 2(22), 3(22), 4(22), 5(22), 6(22) -> 6
        #1(33), 2(33), 3(33), 4(33), 5(33), 6(33) -> 6
        #


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # Idea:
        # 1. Divide and conquer with substructure where:
        #       numRolls(n) = sum(numRolls(n - i) * 5) where 1 <= i <= rollMax[i]
        #
        #    given that number of sequences with length N ending at X is sum of:
        #       number of sequences with length N - 1 ending at non-X
        #       number of sequences with length N - 2 ending at non-X
        #       ...
        #       number of sequences with length N - C ending at non-X
        #
        #    where C is number of repeats from which its not allowed
        #
        # 2. Memorization
        #
        # Time: O(NM) where N is length of sequence, M is max repeat

        memo = [[0] * 6 for _ in range(n)] # memo[n][x] number of sequences of length n ending at x
        # General cases:
        for i in range(n):
            for x in range(6):
                # Sequence with length i ending at x
                maxRolls = rollMax[x]
                for j in range(i - 1, i - 1 - maxRolls, -1):
                    # Sequence with length j ending at non-x
                    if j == -1:
                        memo[i][x] += 1
                        break

                    for y in range(6):
                        if y != x: memo[i][x] += memo[j][y]

        return sum(memo[-1]) % (10 ** 9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # Idea:
        # 1. DP with optimal substructure where:
        #       number of sequences with length N ending at X is sum of:
        #           number of sequences with length N - 1 ending at non-X
        #           number of sequences with length N - 2 ending at non-X
        #           ...
        #           number of sequences with length N - C ending at non-X
        #
        #       where C is number of repeats from which its not allowed
        #
        # Time: O(NM) where N is length of sequence, M is max repeat

        memo = [[0] * 6 for _ in range(n)] # memo[n][x] number of sequences of length n ending at x
        # General cases:
        for i in range(n):
            for x in range(6):
                # Sequence with length i ending at x
                maxRolls = rollMax[x]
                for j in range(i - 1, i - 1 - maxRolls, -1):
                    # Base cases:
                    if j == -1:
                        memo[i][x] += 1
                        break

                    # Sequence with length j ending at non-x
                    for y in range(6):
                        if y != x: memo[i][x] += memo[j][y]

        return sum(memo[-1]) % (10 ** 9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # Idea:
        #   DP with optimal substructure where:
        #       number of sequences of length N ending at X is sum of:
        #           number of sequences of length N - 1 ending at non-X (also seq of len N ending with X)
        #           number of sequences of length N - 2 ending at non-X (also seq of len N ending with XX)
        #           ...
        #           number of sequences of length N - C ending at non-X (also seq of len N ending with XX...X)
        #
        #       where C is number of max repeats
        #
        # Time: O(NM) where N is length of sequence, M is max repeat

        memo = [[0] * 6 for _ in range(n)] # memo[n][x] number of sequences of length n ending at x
        # General cases:
        for i in range(n):
            for x in range(6):
                # Sequence with length i ending at x
                maxRepeats = rollMax[x]
                for j in range(i - 1, i - 1 - maxRepeats, -1):
                    # Base cases:
                    if j == -1:
                        memo[i][x] += 1
                        break

                    # Sequence with length j ending at non-x
                    for y in range(6):
                        if y != x: memo[i][x] += memo[j][y]

        return sum(memo[-1]) % (10 ** 9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[[0] * (max(rollMax) + 1) for _ in range(6)] for _ in range(n)]
        for i in range(6):
            dp[0][i][1] = 1
        mod = 1000000007
        for i in range(n-1):
            for d in range(6):
                for pre in range(6):
                    if pre == d:
                        for cnt in range(rollMax[pre]):
                            dp[i+1][d][cnt + 1] += dp[i][pre][cnt] % mod
                    else:
                        for cnt in range(rollMax[pre] + 1):
                            dp[i+1][d][1] += dp[i][pre][cnt] % mod
        return sum([sum(x) for x in dp[-1]]) % mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[[0] * (max(rollMax) + 1) for _ in range(6)] for _ in range(2)]
        for i in range(6):
            dp[0][i][1] = 1
        mod = 1000000007
        for i in range(n-1):
            idx = i % 2
            dp[1-idx] = [[0] * (max(rollMax) + 1) for _ in range(6)]
            for d in range(6):
                for pre in range(6):
                    if pre == d:
                        for cnt in range(rollMax[pre]):
                            
                            dp[1-idx][d][cnt + 1] += dp[idx][pre][cnt] % mod
                    else:
                        for cnt in range(rollMax[pre ] + 1):
                            dp[1-idx][d][1] += dp[idx][pre][cnt] % mod
        return sum([sum(x) for x in dp[1-n%2]]) % mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # 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])
        dp = [[[0]*16 for _ in range(6)] for _ in range(n)]
        mod = 10**9 + 7
        for j in range(6):
            dp[0][j][1] = 1
        for i in range(1,n):
            for j in range(6):
                for k in range(1,min(rollMax[j]+1,i+2)):
                    if k == 1:
                        for prevj in range(6):
                            if prevj != j:
                                dp[i][j][k] += sum(dp[i-1][prevj])
                    else:
                        dp[i][j][k] = dp[i-1][j][k-1] 
        return sum([dp[-1][j][k] for j in range(6) for k in range(16)]) % mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        def init():
            return [[0 for _ in range(20)] for _ in range(7)]
        st = init()
        pst = init()
        for i in range(1, 7):
            pst[i][1] = 1
            
        for _ in range(1, n):
            for i in range(1, 7):
                st[i][1] = 0
                for j in range(1, 7):
                    if i != j:
                        st[i][1] += sum(pst[j])
                for j in range(2, rollMax[i - 1] + 1):
                    st[i][j] = pst[i][j - 1] % 1000000007
            st, pst = pst, st
        return sum([sum(r) for r in pst]) % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
#         self.rollMax = tuple(rollMax)
        
#         @lru_cache(None)
#         def helper(n, ban):
#             times = 0
#             if n == 1:
#                 for t in ban:
#                     if t > 0:
#                         times += 1
#                 return times

#             for i, t in enumerate(ban):
#                 if t > 0:
#                     cur = tuple()
#                     for j in range(len(ban)):
#                         if i == j:
#                             cur += (ban[j]-1,)
#                         else:
#                             cur += (self.rollMax[j], )
#                     times += helper(n-1, cur)

#             return times % (10**9 + 7)
        
#         return helper(n, tuple(rollMax))
        dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]
        for j in range(len(rollMax)):
            dp[1][j] = 1
            dp[1][-1] += dp[1][j]
        
        for i in range(2, n + 1):
            for j in range(len(rollMax)):
                dp[i][j] = dp[i - 1][-1]
                k = i - rollMax[j]
                if k == 1:
                    dp[i][j] -= 1
                elif k > 1:
                    dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])
                dp[i][-1] += dp[i][j]
        return dp[n][len(rollMax)] % int(1e9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        def init():
            return [[0 for _ in range(20)] for _ in range(7)]
        st = init()
        pst = init()
        for i in range(1, 7):
            pst[i][1] = 1
            
        for _ in range(1, n):
            for i in range(1, 7):
                st[i][1] = 0
                for j in range(1, 7):
                    if i != j:
                        st[i][1] += sum(pst[j])
                for j in range(2, rollMax[i - 1] + 1):
                    st[i][j] = pst[i][j - 1]
            st, pst = pst, st
        return sum([sum(r) for r in pst]) % 1000000007

from functools import lru_cache

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        if n < 1:
            return 0
        
        @lru_cache(maxsize=None)
        def backtrack(prev_roll, count, seq_len):
            if seq_len == n:
                return 1

            result = 0

            for num in range(6):
                if num != prev_roll:
                    result += backtrack(num, 1, seq_len+1)
                elif count < rollMax[num]:
                    result += backtrack(num, count+1, seq_len+1)

            return result % MOD
        
        MOD = (10 ** 9) + 7
        return backtrack(-1, 0, 0)


from typing import List
import collections
import heapq
import itertools
import bisect
import copy
import random
import re
import fractions
import math

mod = 10 ** 9 + 7


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

        rollMax = [0] + rollMax
        dp = [[[0] * 17 for _ in range(7)] for _2 in range(n)]
        dp[0] = [[0, 1] + [0] * 15 for _ in range(7)]

        for m in range(1, n):
            for i in range(1, 7):
                for j in range(1, 7):
                    for k in range(1, rollMax[j] + 1):  # we could extend j no more
                        if i == j:
                            if k < rollMax[i]:
                                dp[m][i][k + 1] += dp[m-1][i][k] % mod
                        else:
                            dp[m][i][1] += dp[m-1][j][k] % mod


        return sum(map(sum, dp[n-1])) % mod


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10**9 + 7
        # dp[i][j] records the value of sequence of i elements with j being the last element
        dp = [[0]*7 for _ in range(n+1)]
        # initialize
        dp[0][0] = 1
        for i in range(1,7):
            dp[1][i] = 1
        for i in range(2,n+1):
            for j in range(1,7):
                for z in range(7):
                    if j==z:
                        continue
                    for k in range(1,min(rollMax[j-1],i)+1):
                        dp[i][j] += dp[i-k][z]
                        dp[i][j] %= mod
        return sum([dp[n][i] for i in range(1,7)])%mod
            


MOD = 1000000007
class Solution:
    def dieSimulator(self, n, rollMax):
        r = max(rollMax)
        dp = [[0] * (r + 1) for _ in range(6)]
        # dp[i][j] last roll was i and i was thrown j consecutive times
        for i in range(6):
            dp[i][1] = 1
        for _ in range(n - 1):
            tmp = [[0] * (r + 1) for _ in range(6)]
            for i in range(6):
                for j in range(6):
                    if i != j:
                        for k in range(rollMax[i] + 1):
                            tmp[j][1] += dp[i][k]
                    else:
                        for k in range(rollMax[i]):
                            tmp[j][k + 1] += dp[j][k]
                   
            dp = tmp
        res = 0
        for j in range(6):
            for k in range(r + 1):
                res = (res + dp[j][k]) % MOD
        return res % MOD

MOD = 1000000007
class Solution:
    def dieSimulator(self, n, rollMax):
        r = max(rollMax)
        dp = [[0] * (r + 1) for _ in range(6)]
        # dp[i][j] last roll was i and i was thrown j consecutive times
        for i in range(6):
            dp[i][1] = 1
        for _ in range(n - 1):
            tmp = [[0] * (r + 1) for _ in range(6)]
            for i in range(6):
                for j in range(6):
                    if i != j:
                        for k in range(rollMax[i] + 1):
                            tmp[j][1] += dp[i][k]
                    else:
                        for k in range(rollMax[i]):
                            tmp[j][k + 1] += dp[j][k]
            dp = tmp
        return sum(dp[j][k] for j in range(6) for k in range(r + 1)) % MOD

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]
        for j in range(len(rollMax)):
            dp[1][j] = 1
            dp[1][-1] += dp[1][j]
        
        for i in range(2, n + 1):
            for j in range(len(rollMax)):
                dp[i][j] = dp[i - 1][-1]
                k = i - rollMax[j]
                if k == 1:
                    dp[i][j] -= 1
                elif k > 1:
                    dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])
                dp[i][-1] += dp[i][j]
        return dp[n][len(rollMax)] % int(1e9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        table = [[0 for i in range(n+1)] for j in range(7)]
        
        def helper( n: int, rollMax: List[int], last: int ) -> int:
            if n==0:
                return 1
            if table[last][n] > 0:
                return table[last][n]
            
            total = 0
            for i in range(1,7):
                if i==last:
                    continue
                for j in range(1,rollMax[i-1]+1):
                    if j > n:
                        break
                    total += helper(n-j, rollMax, i)
            table[last][n] = total%1000000007
            return total%1000000007
        
        ans = helper(n, rollMax, -1)
        print(table)
        
        return table[-1][-1]

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[[0] * 16 for _ in range(6)] for _ in range(n+1)]
        MOD = 10 ** 9 + 7
        for i in range(6):
            dp[1][i][1] = 1
            
        for i in range(2, n+1):
            for j in range(6):
                for p in range(6):
                    for k in range(1, rollMax[p]+1):
                        if j != p:
                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k]) % MOD
                        elif k < rollMax[j]:
                            dp[i][j][k+1] = dp[i-1][j][k]
        ans = 0
        for i in range(6):
            for k in range(1, rollMax[i]+1):
                ans = (ans + dp[n][i][k]) % MOD
        return ans
        


class Solution:
    def dieSimulator(self, n, rollMax):
        K = max(rollMax)
        dp = [[[0 for k in range(K)] for j in range(6)] for i in range(n)] 
        for j in range(6): dp[0][j][0] = 1
        for i in range(1, n):
            for j in range(6):
                dp[i][j][0] += sum(dp[i-1][t][k] for t in range(6) for k in range(rollMax[t]) if t != j)
                for k in range(1, min(rollMax[j],i+1)):
                    dp[i][j][k] = dp[i-1][j][k-1]
        return sum(dp[n-1][j][k] for j in range(6) for k in range(K)) % (10**9+7)
    
    
    #https://leetcode.com/problems/dice-roll-simulation/discuss/403862/Python-O(N)-Bottom-Up-DP-with-explaination


class Solution:
    def dieSimulator(self, n, rollMax):
        K = max(rollMax)
        dp = [[[0 for _ in range(K)] for _ in range(6)] for _ in range(n)] 
        for j in range(6): dp[0][j][0] = 1
        for i in range(1, n):
            for j in range(6):
                dp[i][j][0] += sum(dp[i-1][t][k] for t in range(6) for k in range(rollMax[t]) if t != j)
                for k in range(1, min(rollMax[j],i+1)):
                    dp[i][j][k] = dp[i-1][j][k-1]
        return sum(dp[n-1][j][k] for j in range(6) for k in range(K)) % (10**9+7)
    
    
    #https://leetcode.com/problems/dice-roll-simulation/discuss/403862/Python-O(N)-Bottom-Up-DP-with-explaination


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        modulo = 10**9 + 7
        dp = [[0 for _ in range(6)] for _ in range(n)]
        
        for roll in range(n):
            for number in range(6):
                for limit in range(1, rollMax[number]+1):
                    if roll >= limit:
                        for possibility in range(6):
                            if possibility != number:
                                dp[roll][number] = (dp[roll][number] + dp[roll-limit][possibility])%modulo
                    else:
                        dp[roll][number] += 1
                        break
                
    
        return sum(dp[n-1])%modulo

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]
        for j in range(len(rollMax)):
            dp[1][j] = 1
            dp[1][-1] += dp[1][j]
        
        for i in range(2, n + 1):
            for j in range(len(rollMax)):
                dp[i][j] = dp[i - 1][-1]
                k = i - rollMax[j]
                if k == 1:
                    dp[i][j] -= 1
                elif k > 1:
                    dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])
                dp[i][-1] += dp[i][j]
        return dp[n][len(rollMax)] % int(1e9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        maxAns = 10**9 + 7
        krollMax = 15
        
        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]
        # [n+1][6][15+1]
        
        for i in range(6):
            dp[1][i][1] = 1
        
        for i in range(2,n+1):
            for j in range(6):#current dice num
                for p in range(6): # previous dice num 
                    for k in range(1, rollMax[p]+1):
                        # if k>rollMax[p]: continue
                        if j != p: #different than previous dice
                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns
                        elif k<rollMax[j]:
                            dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns
                    # for k in range(1, krollMax+1):
                    #     if k>rollMax[p]: continue
                    #     if j != p: #different than previous dice
                    #         dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns
                    #     elif k<rollMax[j]:
                    #         dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns
        ans = 0
        for i in range(6):
            for j in range(rollMax[i]+1):
                ans += dp[n][i][j]
        return ans % maxAns
                            
                    
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 7 + 1e9
        @lru_cache(maxsize=None)
        def helper(idx, roll, turn):
            if roll > rollMax[idx]:
                return 0

            if turn == n:
                return 1

            result = 0
            if idx == -1:
                for i in range(len(rollMax)):
                    result = (result + helper(i, 1, turn + 1)) % MOD
            else:
                for i in range(len(rollMax)):
                    if i == idx:
                        result = (result + helper(i, roll + 1, turn + 1)) % MOD
                    else:
                        result = (result + helper(i, 1, turn + 1)) % MOD
            return result

        return int(helper(-1, 0, 0) % MOD)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * 7 for _ in range(n+1)]
        dp[1][1:] = [1] * 6
        for i in range(2, n+1):
            for j in range(1, 7):
                for k in range(1, rollMax[j-1]+1):
                    if i-k < 0:
                        break
                    elif i-k == 0:
                        dp[i][j] += 1
                    else:
                        dp[i][j] += sum([dp[i-k][l] for l in range(1, 7) if l != j])
        return sum(dp[-1]) % (10**9+7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        kmax = 15
        kmod = pow(10, 9) + 7
        
        # dp[i][j][k]: # of sequences ends with k consecutive j after i rolls
        dp = [[[0] * (kmax + 1) for _ in range(6)] for _ in range(n + 1)]
        
        for j in range(6):
            dp[1][j][1] = 1
            
        for i in range(2, n + 1):
            for j in range(6):
                for p in range(6):
                    for k in range(1, rollMax[p] + 1):
                        if p != j:
                            dp[i][j][1] = (dp[i][j][1] + dp[i - 1][p][k]) % kmod
                        elif k < rollMax[p]:
                            dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i - 1][p][k]) % kmod
                            
        ans = 0
        for j in range(6):
            for k in range(1, rollMax[j] + 1):
                ans = (ans + dp[n][j][k]) % kmod
                
        return ans


from functools import lru_cache

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        @lru_cache(None)
        def dfs(rolls_left, prev_roll, num_repeats):
            if rolls_left == 0:
                return 1
            ans = 0
            for roll in range(6):
                if roll == prev_roll:
                    if rollMax[roll] - num_repeats > 0:
                        ans += dfs(rolls_left-1, prev_roll, num_repeats+1)
                else:
                    ans += dfs(rolls_left-1, roll, 1)
            return ans % (10**9 + 7)
        
        return dfs(n, -1, 0)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        M = pow(10, 9) + 7
        rollMax = [0] + rollMax
        dp = [[[0] * (15 + 1) for _ in range(6 + 1)] for _ in range(n + 1)]
        
        # 抛第一次骰子，出现数字 i 的次数
        for i in range(1, 6 + 1):
            dp[1][i][1] = 1
        
        for i in range(2, n + 1): # 第 i 次抛
            for j in range(1, 6 + 1): # 得到骰子的num数
                for k in range(1, rollMax[j] + 1): # 这个数字第 k次出现
                    if k > 1:
                        dp[i][j][k] = dp[i-1][j][k-1]
                    else:
                        for jj in range(1, 6 + 1):
                            for kk in range(1, rollMax[jj] + 1):
                                if jj != j:
                                    dp[i][j][k] += dp[i-1][jj][kk]
        
        res = 0
        for i in range(1, 7):
            for j in range(1, rollMax[i] + 1):
                res += dp[n][i][j]
        return res % M

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        dp =collections.deque([[1] * 7 for i in range(max(rollMax) + 1)])
        dp[-1][-1] = 6
        for i in range(2,  n + 1):
            dp2 = [0] * 7
            for j in range(6):
                if i - rollMax[j] <= 0:
                    dp2[j] = dp[-1][-1]
                elif i - rollMax[j] == 1:
                    dp2[j] = dp[-1][-1] - 1 
                else:
                    p = dp[-rollMax[j] - 1]
                    dp2[j] = (dp[-1][-1] - p[-1] + p[j]) % MOD
                dp2[-1] = (dp2[-1] + dp2[j]) % MOD
            dp.popleft()
            dp.append(dp2)
        return dp[-1][-1]


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]
        for j in range(len(rollMax)):
            dp[1][j] = 1
        
        dp[1][-1] = 6
        
        for i in range(2, n + 1):
            for j in range(len(rollMax)):
                dp[i][j] = dp[i - 1][-1]
                k = i - rollMax[j]
                if k == 1:
                    dp[i][j] -= 1
                elif k > 1:
                    dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])
                dp[i][-1] += dp[i][j]
                
        return dp[n][len(rollMax)] % (10**9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * (n+1) for _ in range(6)]
        
        for roll in range(1, n+1):
            for face in range(6):
                if roll == 1:
                    dp[face][roll] = 1
                else:
                    for k in range(1, rollMax[face]+1):
                        if roll - k < 0:
                            break
                        elif roll - k == 0:
                            dp[face][roll] += 1
                        else:
                            for l in range(6):
                                if l != face:
                                    dp[face][roll] += dp[l][roll-k]
        
        res = 0 
        for i in range(6):
            res += dp[i][-1]
        
        return res % (10**9 + 7)

#[] DP
#O(6N * 6T): T: upperbound of rollMax

#f(i, d): number of combinations of res[0~i] if the last number is d
#f(i, ?) = 1 if i == 0
#               d'd d d ... d [d]
#               ? d'd d ... d [d]
#               ? ? d'd ... d [d]
#               ? ? ? d'... d [d]
#               ? ? ? ? ... d'[d]
#f(i, d) = sum{ f(j, d') for j in i-rollMax[d] ~ i-1 for d' in 0~5
#               if i-rollMax[d] >= 0 and d' != d }
#          sum{ f(i-1, d') for any d' if rollMax[d] < i} < no limit
MOD = 1000000007
def memorized(f):
    memo = {}
    def helper(*arg):
        if arg not in memo:
            memo[arg] = f(*arg)
        return memo[arg]
    return helper
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @memorized
        def f(i: int, d: int):
            if i == 0:
                return 1
            if i >= rollMax[d]:
                return sum(f(j, d2) for j in range(i-rollMax[d], i) for d2 in range(6) if d2 != d) % MOD
            else:
                return sum(f(i-1, d2) for d2 in range(6)) % MOD
        return sum(f(n-1, d) for d in range(6)) % MOD

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dp[i][j][k] means this is ith roll and we end up with number j and it has lasted k times
        dp = [[[0 for k in range(16)] for j in range(7)] for i in range(n + 1)]
        mod = pow(10, 9) + 7
        
        for j in range(1, 7):
            dp[1][j][1] = 1
        
        for i in range(2, n + 1):
            for j in range(1, 7):
                for prev in range(1, 7):
                    for k in range(1, rollMax[prev - 1] + 1):
                        if j != prev:
                            dp[i][j][1] = (dp[i][j][1] + dp[i - 1][prev][k]) % mod
                        else:
                            if k < rollMax[prev - 1]:
                                dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i - 1][j][k])
        
        ans = 0
        for j in range(1, 7):
            for k in range(1, rollMax[j - 1] + 1):
                ans = (ans + dp[n][j][k]) % mod
        
        return ans

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        @lru_cache(None)
        def roll(i, j, k):
            if i == 0:
                return 1
            cnt = 0 
            for d in range(6):
                if d == j:
                    if k < rollMax[j]:
                        cnt = (cnt + roll(i - 1, d, k + 1)) % MOD
                else:
                    cnt = (cnt + roll(i - 1, d, 1)) % MOD
            return cnt
        
        return roll(n, -1, 0)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[[0 for k in range(16)] for j in range(6)] for i in range(n)]
        
        for s in range(6):
            dp[0][s][1] = 1
            
        for i in range(1,n):
            for j in range(6):
                for k in range(1,rollMax[j]+1):
                    if k > 1:
                        dp[i][j][k] = dp[i-1][j][k-1]
                    else:
                        for jj in range(6):
                            for kk in range(1,rollMax[jj]+1):
                                if j == jj:
                                    continue
                                dp[i][j][k] += dp[i-1][jj][kk]
        ans = 0
        for l in range(6):
            for m in range(1,rollMax[l]+1):
                ans += dp[n-1][l][m]
        
        return ans%(10**9+7)
                    
                        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0]*(len(rollMax)+1) for _ in range(n+1)]
        
        for idx in range(len(rollMax)):
            dp[1][idx] = 1
            dp[1][-1] += dp[1][idx]
        
        for row in range(2, n+1):
            for col in range(len(rollMax)):
                dp[row][col] = dp[row-1][-1]
                
                delta = row-rollMax[col]
                
                if delta == 1:
                    dp[row][col] -= 1
                elif delta > 1:
                    dp[row][col] -= (dp[delta-1][-1] - dp[delta-1][col])
                
                dp[row][-1] += dp[row][col]
        
        return dp[n][len(rollMax)] % (pow(10,9)+7)

class Solution:
    #dp[i][j][k] c!=k dp[i-1][j-1][c]
    #dp[i][j][k]
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        #from inner to outer 
        dp=[[[0 for k in range(16)] for j in range(6)] for i in range(n)]
        #print(len(dp),len(dp[0]),len(dp[0][0]))
        mod=1e9+7
        for i in range(6):
            dp[0][i][1]=1
        #print(dp)
        for i in range(1,n):
            for j in range(6):
                for k in range(1,16):
                    if k==1:
                        for jj in range(6):
                            for kk in range(1,rollMax[jj]+1):
                                if j!=jj:
                                    # print(kk,jj,i,j,k)
                                    try:
                                        dp[i][j][k]=(dp[i][j][k]+dp[i-1][jj][kk])%mod
                                    except IndexError as e:
                                        print((kk,jj,i,j,k))
                    else:
                        dp[i][j][k]=dp[i-1][j][k-1]
        res=0
        for j in range(6):
            for k in range(1, rollMax[j]+1):
                res=(res+dp[n-1][j][k])%mod
        return int(res)
                                


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dynamic programming
        # dp[i][j][k] # at pos i, we end with j, and the number of continuous of j at the end is k

        dp = [ [ [ 0 for k in range(rollMax[j] + 1)] for j in range(6)] for _ in range(n)]
        
        for j in range(6):
            dp[0][j][1] = 1
        
        for i in range(n):
            for j in range(6):
                for k in range(2, rollMax[j] + 1):
                    dp[i][j][k] += dp[i - 1][j][k - 1]
                
                for otherj in range(6):
                    if otherj != j:
                        for k in range(1, rollMax[otherj] + 1):
                            dp[i][j][1] += dp[i - 1][otherj][k]
        # print(\"dp=\", dp)
        return sum([sum(x)%(10**9 + 7) for x in dp[-1]])%(10**9 + 7)
# 题解，这种计算个数的一般都是动态规划。注意到题目中 rollMax[i] >=1说明 只要上一个不一样，那么我这次出那个数字都是可以的。最后别忘了求 mod
# 动态规划， 最重要的是，要记录哪种状态。这里 要求的是 某个 number 不能连续超过 rollMax[j]次，那么显然我们需要记录这件事。然后当前的位置需要记录，最后一个数字是什么需要记录，最后一个数字出现多少次，需要记录，于是三维 dp 出现了。

#dp[i][j][k] 代表 到第 i 个位置时，以数字 j 结尾，结尾处 连续出现 k 次。 那么其实这里就要求 k >= 1 的，因为以 j结尾了，那么肯定至少有一个数字了。
# dp 三维数组的维度怎么确定呢？ i，j 是很显然，一个是 n，一个是6，那么k维度，我们用 roolMax[j] + 1 这个维度，因为 我们出现的个数 0，1，2，3，4，。。。，一直到 roolMax[j] 都是可以的，所以 range （roolMax[j] + 1).
# 那么 j 用 range(6) = 0, 1, 2, 3, 4,5 这里是没有关系的，正好和 roolMax[j] 的 index 对应起来。 不用 换成 1，2，3，4，5，6.


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dynamic programming
        # dp[i][j][k] # at pos i, we end with j, and the number of continuous of j at the end is k

        dp = [ [ [ 0 for k in range(rollMax[j] + 1)] for j in range(6)] for _ in range(n)]
        
        for j in range(6):
            dp[0][j][1] = 1
        
        for i in range(n):
            for j in range(6):
                for k in range(2, rollMax[j] + 1): # 这里 原则上来说应该写成 range(2)开始，因为 k-1>=1,但是写成 1也没有关系，因为 k-1=0, += 0, 没有影响。
                    dp[i][j][k] += dp[i - 1][j][k - 1]
                
                for otherj in range(6):
                    if otherj != j:
                        for k in range(1, rollMax[otherj] + 1):
                            dp[i][j][1] += dp[i - 1][otherj][k]
        # print(\"dp=\", dp)
        return sum([sum(x)%(10**9 + 7) for x in dp[-1]])%(10**9 + 7)
# 题解，这种计算个数的一般都是动态规划。注意到题目中 rollMax[i] >=1说明 只要上一个不一样，那么我这次出那个数字都是可以的。最后别忘了求 mod
# 动态规划， 最重要的是，要记录哪种状态。这里 要求的是 某个 number 不能连续超过 rollMax[j]次，那么显然我们需要记录这件事。然后当前的位置需要记录，最后一个数字是什么需要记录，最后一个数字出现多少次，需要记录，于是三维 dp 出现了。

#dp[i][j][k] 代表 到第 i 个位置时，以数字 j 结尾，结尾处 连续出现 k 次。 那么其实这里就要求 k >= 1 的，因为以 j结尾了，那么肯定至少有一个数字了。
# dp 三维数组的维度怎么确定呢？ i，j 是很显然，一个是 n，一个是6，那么k维度，我们用 roolMax[j] + 1 这个维度，因为 我们出现的个数 0，1，2，3，4，。。。，一直到 roolMax[j] 都是可以的，所以 range （roolMax[j] + 1).
# 那么 j 用 range(6) = 0, 1, 2, 3, 4,5 这里是没有关系的，正好和 roolMax[j] 的 index 对应起来。 不用 换成 1，2，3，4，5，6.


import collections as clc
import functools as ft


class Solution:
    
    BASE = 10 ** 9 + 7
    
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        state = clc.defaultdict(int)
        state[1, 0] = 1
        for _ in range(n):
            new_state = clc.defaultdict(int)
            for (last_roll, streak), count in list(state.items()):
                for dice in range(1, 7):
                    if dice == last_roll:
                        if streak >= rollMax[last_roll - 1]:
                            continue
                        new_state[dice, streak + 1] = (new_state[dice, streak + 1] + count) % self.BASE
                    else:
                        new_state[dice, 1] = (new_state[dice, 1] + count) % self.BASE
            state = new_state
        return sum(state.values()) % self.BASE


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dynamic programming
        # dp[i][j][k] # at pos i, we end with j, and the number of continuous of j at the end is k
        
        dp = [ [ [ 0 for k in range(rollMax[j] + 1)] for j in range(6)] for _ in range(n)]
        
        for j in range(6):
            dp[0][j][1] = 1
        
        for i in range(n):
            for j in range(6):
                for k in range(1, rollMax[j] + 1):
                    dp[i][j][k] += dp[i - 1][j][k - 1]
                
                for otherj in range(6):
                    if otherj != j:
                        for k in range(1, rollMax[otherj] + 1):
                            dp[i][j][1] += dp[i - 1][otherj][k]
        # print(\"dp=\", dp)
        return sum([sum(x)%(10**9 + 7) for x in dp[-1]])%(10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        states = {(None, 1): 1}
        
        for _ in range(n):
            new_states = collections.defaultdict(int)
            for state, count in list(states.items()):
                for i in range(1, 7):
                    if i == state[0]:
                        if state[1] + 1 <= rollMax[i - 1]:
                            new_states[(i, state[1] + 1)] += count
                    else:
                        new_states[(i, 1)] += count
            states = new_states
        return sum(states.values()) % (10 ** 9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        maxRolls = min(n, max(rollMax))
        dp = [[[0] * (maxRolls + 1) for _ in range(7)] for _ in range(n + 1)]
        
        # Base case
        for j in range(1, 7):
            dp[1][j][1] = 1
        
        for i in range(2, n + 1):
            for j in range(1, 7):
                for k in range(1, min(i, rollMax[j - 1]) + 1):
                    if k > 1:
                        # Last roll was also a j
                        dp[i][j][k] = sumMod(dp[i][j][k], dp[i - 1][j][k - 1])
                        continue
                    
                    # Last roll was a jj != j
                    for jj in range(1, 7):
                        if jj == j:
                            continue

                        for kk in range(1, min(i - 1, rollMax[jj - 1]) + 1):
                            dp[i][j][k] = sumMod(dp[i][j][k], dp[i - 1][jj][kk])
        
        result = 0
        for j in range(1, 7):
            for k in range(1, min(n, rollMax[j - 1]) + 1):
                result = sumMod(result, dp[n][j][k])
        
        return result
    
    
def sumMod(x: int, y: int) -> int:
    return (x + y) % (10 ** 9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * 7 for _ in range(n)]
        for j in range(6):
            dp[0][j] = 1
        dp[0][-1] = 6
        
        for i in range(1, n):
            total = 0
            for j in range(6):
                dp[i][j] = dp[i - 1][-1]
                if i - rollMax[j] == 0:
                    dp[i][j] -= 1
                if i - rollMax[j] >= 1:
                    dp[i][j] -= dp[i - rollMax[j] - 1][-1] - dp[i - rollMax[j] - 1][j]
                total += dp[i][j]
            dp[i][-1] = total
            
        return dp[-1][-1] % (10 ** 9 + 7)
                    


from functools import lru_cache
class Solution:    
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10 ** 9 + 7

        @lru_cache(None)
        def dfs(n, last_idx, curr_len):
            if n == 0:
                return 1
            
            cnt = 0     
            for i in range(6):
                if i != last_idx or curr_len < rollMax[i]:
                    temp = 1 if i != last_idx else curr_len + 1
                    cnt += dfs(n-1, i, temp)
            return cnt % mod
        return dfs(n, -1, 0)
                    
                    
            


import functools

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

        @functools.lru_cache(None)
        def count_sequences(last_index, last_remaining, rolls_left):
            if last_remaining < 0:
                return 0
            if rolls_left == 0:
                return 1

            sequences_from_here = 0
            for i in range(len(rollMax)):
                if i == last_index:
                    sequences_from_here += count_sequences(i, last_remaining - 1, rolls_left - 1)
                else:
                    sequences_from_here += count_sequences(i, rollMax[i] - 1, rolls_left - 1)
            return sequences_from_here % (10 ** 9 + 7)

        return sum(count_sequences(i, rollMax[i] - 1, n - 1) for i in range(len(rollMax))) % (10 ** 9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = {(i, 1):1 for i in range(6)}
        mod = 10**9+7
        for _ in range(1, n):
            dp2 = {}
            for r, t in dp:
                for i in range(6):
                    if r==i:
                        if t==rollMax[i]:
                            continue
                        else:
                            dp2[(r, t+1)] = dp[(r, t)]%mod
                    else:
                        dp2[(i, 1)] = (dp2.get((i, 1), 0)+dp[(r, t)])%mod
            
            dp = dp2
        
        return sum(dp.values())%mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        self.total = 0
        
        @lru_cache(maxsize = 1000) 
        def digit(last,lastcount,k):
            if k == n:
                return 1
                            
            curnum= 0
            
            for i in range(6):
                if i == last and k != 0:
                    curcount = lastcount + 1
                else:
                    curcount = 1
                    
                if rollMax[i] < curcount:
                    continue
                else:            
                    curnum += digit(i,curcount,k+1)
            return curnum%(10**9+7)
        
        return digit(0,0,0)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        from functools import lru_cache
        @lru_cache(maxsize = None)
        def bt(dieLeft, lastVal, lastConsecCount):
            if dieLeft == 0:
                return 1
            
            total = 0
            for i in range(0, 6):
                if i == lastVal and lastConsecCount == rollMax[i]:
                    continue
                else:
                    if i == lastVal:
                        newCount = lastConsecCount + 1
                        #print(lastVal, lastConsecCount)
                    else:
                        newCount = 1
                    
                    total += bt(dieLeft - 1, i, newCount)
                    if total > 10**9 + 7:
                        total = total % (10**9 + 7)
            return total
        
        return bt(n, None, None)
        
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        from collections import defaultdict
        LARGE = int(1e9+7)
        
        die_prev_to_combination = {(i,1):1 for i in range(1,7)}
        for i in range(n-1):
            next_die_prev_to_combination = defaultdict(int)
            for die_and_prev, combination in list(die_prev_to_combination.items()):
                die, prev = die_and_prev
                for next_die in range(1,7):
                    if next_die==die:
                        if prev==rollMax[die-1]:
                            continue
                        else:
                            next_die_prev_to_combination[(next_die, prev+1)] += combination
                    else:
                        next_die_prev_to_combination[(next_die,1)] += combination
            die_prev_to_combination = next_die_prev_to_combination
            
        return sum(c for d,c in list(die_prev_to_combination.items()))%LARGE


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

        @lru_cache(None)
        def dfs(residual, last, lastFre):
            if residual == 0:
                return 1
            tmp = 0
            if rollMax[last - 1] == lastFre:
                for i in range(6):
                    if i + 1 == last:
                        continue
                    tmp += dfs(residual - 1, i + 1, 1) % (10**9 + 7)
            else:
                for i in range(6):
                    if i + 1 == last:
                        tmp += dfs(residual - 1, last, lastFre + 1)% (10**9 + 7)
                    else:
                        tmp += dfs(residual - 1, i + 1, 1)% (10**9 + 7)
            return tmp % (10**9 + 7)
        
        ans = 0
        for j in range(1, 7):
            ans += dfs(n-1, j, 1)
            ans %=  (10**9 + 7)
        return ans 


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        memo = {}
        def helper(n, lastnum):
            if n == 0:
                return 1
            if (n, lastnum) in memo:
                return memo[(n, lastnum)]
            
            res = 0
            for num in range(6):
                if num == lastnum: continue
                for i in range(1, rollMax[num]+1):
                    nxtn = n-i
                    if nxtn < 0: break
                    res += helper(nxtn, num)
            memo[(n, lastnum)] = res%(10**9 + 7)
            return memo[(n, lastnum)]
        
        return helper(n, None)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 1000000007
        if (n == 0): return 0
        dp = [[[0]*(max(rollMax)+2) for _ in range(7)] for __ in range(n+1)]
        for i in range(1,7):
            if (rollMax[i-1] > 0):
                dp[1][i][1] = 1
        for x in range(2,n+1):
            for i in range(1,7):
                for k in range(1, rollMax[i-1]):
                    dp[x][i][k+1] = (dp[x-1][i][k])%MOD
                for j in range(1,7):
                    if (j == i): continue
                    for k in range(1,rollMax[i-1]+1):
                        dp[x][j][1] = (dp[x][j][1]+dp[x-1][i][k])%MOD
        num = 0
        for i in range(1,7):
            for k in range(1,max(rollMax)+1):
                num = (num + dp[n][i][k]) % MOD
        return num
            


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

#         dp = [[0] * 7 for _ in range(n)]
#         dp[0] = [1] * 6 + [6]
        
#         for j in range(1, n):
#             for i in range(6):
                
#                 dp[j][i] = dp[j - 1][-1]
#                 k = j - rollMax[i]
                
#                 if k == 0:
#                     dp[j][i] -= 1
                
#                 elif k > 0:
#                     dp[j][i] -= (dp[k - 1][-1] - dp[k - 1][i])
                    
#                 # dp[i][-1] += dp[i][j]
#             dp[i][6] = sum(dp[i][:6])
                
#         print (dp)
                
#         return dp[n-1][len(rollMax)] % int(1e9 + 7)
        

        dp = [[0] * 7 for _ in range(n)]
        dp[0] = [1] * 6 + [6]

        for r in range(1, n):
            for c in range(6):
                
                dp[r][c] = dp[r-1][-1]
                
                k = r - rollMax[c]

                if k == 0: # when all numbers = i
                    dp[r][c] -= 1
                    
                elif k >= 1: # when we have prefix
                    dp[r][c] -= (dp[k-1][-1] - dp[k-1][c])
                
            dp[r][6] = sum(dp[r][:6])
            
        # print (dp)
            
        return dp[-1][-1] % int(1e9 + 7)
                    


from collections import defaultdict

class Solution:
  def dieSimulator(self, n: int, rollMax: List[int]) -> int:
    # O(15 x 6 x N)
    M = 10 ** 9 + 7
    # at i-th roll, count (last-roll, num consecutive rolls of same with last roll): num of combinations
    q = {(-1, 0): 1}
    for _ in range(n):
      p = defaultdict(lambda: 0)
      for x, r in q:
        for y in range(6):
          if y == x:
            if r + 1 <= rollMax[y]:
              p[(y, r + 1)] += q[(x, r)] % M
          else:
            p[(y, 1)] += q[(x, r)] % M
      q = p
    return sum(q.values()) % M


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = (10 ** 9) + 7
        @lru_cache(maxsize=None)
        def solve(n, last, last_count):
            if n == 0:
                return 1
            ans = 0
            for i in range(6):
                if i == last and last_count > 0:
                    ans += solve(n - 1, last, last_count - 1)
                elif i != last and rollMax[i] > 0:
                    ans += solve(n - 1, i, rollMax[i] - 1)
            return ans % MOD
        
        return solve(n, -1, -1)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        maxRolls = min(n, max(rollMax))
        dp = [[[0] * (maxRolls + 1) for _ in range(7)] for _ in range(2)]
        
        # Base case
        for j in range(1, 7):
            dp[1][j][1] = 1
        
        for i in range(2, n + 1):
            iMod2 = i % 2
            iMinus1Mod2 = (i - 1) % 2
            
            for j in range(1, 7):
                # Last roll was a jj != j
                dp[iMod2][j][1] = 0
                for jj in range(1, 7):
                    if jj == j:
                        continue
                    for kk in range(1, min(i - 1, rollMax[jj - 1]) + 1):
                        dp[iMod2][j][1] = sumMod(dp[iMod2][j][1], dp[iMinus1Mod2][jj][kk])
                
                # Last roll was also a j
                for k in range(2, min(i, rollMax[j - 1]) + 1):
                    dp[iMod2][j][k] = dp[iMinus1Mod2][j][k - 1]
        
        result = 0
        nMod2 = n % 2
        for j in range(1, 7):
            for k in range(1, min(n, rollMax[j - 1]) + 1):
                result = sumMod(result, dp[nMod2][j][k])
        
        return result
    
    
def sumMod(x: int, y: int) -> int:
    return (x + y) % (10 ** 9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10**9 + 7
        
        dp = [[0, 1] + [0] * 15 for i in range(6)]
        
        for _ in range(n - 1):
            dp2 = [[0] * 17 for i in range(6)]
            for i in range(6):
                for k in range(1, rollMax[i] + 1):
                    for j in range(6):
                        if i == j:
                            if k < rollMax[i]:
                                dp2[j][k + 1] += dp[i][k] % mod
                        else:
                            dp2[j][1] += dp[i][k] % mod
            dp = dp2
        
        return sum(sum(row) for row in dp) % mod


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        self.total = 0
        
        @lru_cache(maxsize = 100000000)
        #memo = [[[-1 for _ in range(n)] for _ in range(max(rollMax)+1)] for _ in range(6)]
        def digit(last,lastcount,k):          
            if k == n:
                return 1    
           # elif memo[last][lastcount][k] != -1:
                #return memo[last][lastcount][k]
            curnum= 0
            
            for i in range(6):
                if i == last and k != 0:
                    curcount = lastcount + 1
                else:
                    curcount = 1
                    
                if rollMax[i] < curcount:
                    continue
                else:            
                    curnum += digit(i,curcount,k+1)
            #memo[last][lastcount][k] = curnum%(10**9+7)
            return curnum%(10**9+7)#memo[last][lastcount][k]
        
        return digit(0,0,0)



class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.ans = 0
        @lru_cache(maxsize=None)
        def rec(index,k,num):
            if index == n:
                return 1
            ans = 0 
            for i in range(6):
                if i!=k:
                    ans += rec(index+1,i,1)
                elif num+1 <= rollMax[i]:
                    ans += rec(index+1,i,num+1)
            return ans
                
       
        
            
        return rec(0,-1,0)% ((10**9)+7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        self.total = 0
        
        @lru_cache(maxsize = 100000)
        #memo = [[[-1 for _ in range(n)] for _ in range(max(rollMax)+1)] for _ in range(6)]
        def digit(last,lastcount,k):          
            if k == n:
                return 1    
           # elif memo[last][lastcount][k] != -1:
                #return memo[last][lastcount][k]
            curnum= 0
            
            for i in range(6):
                if i == last and k != 0:
                    curcount = lastcount + 1
                else:
                    curcount = 1
                    
                if rollMax[i] < curcount:
                    continue
                else:            
                    curnum += digit(i,curcount,k+1)
            #memo[last][lastcount][k] = curnum%(10**9+7)
            return curnum%(10**9+7)#memo[last][lastcount][k]
        
        return digit(0,0,0)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @lru_cache(maxsize=None)
        def dfs(n, i, k):
            if not n: return 1
            ans = 0
            for j in range(6):
                if i != j: ans += dfs(n-1, j, 1)
                elif k+1 <= rollMax[j]: ans += dfs(n-1, j, k+1)
            return ans    
        return sum(dfs(n-1, i, 1) for i in range(6)) % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        memo = {}
        def die_simulator_starting_at(start: int, n: int):
            if (start, n) in memo:
                return memo[start, n]
            if n == 1:
                memo[start, n] = 1
            else:
                count = 0
                for j in range(1, min(n, rollMax[start] + 1)):
                    for nxt in range(6):
                        # hack to count a run of \"start\"s at the end
                        if nxt != start or j == n - 1 and j < rollMax[start]:
                            count = (count + die_simulator_starting_at(nxt, n - j)) % 1000000007
                memo[start, n] = count
            return memo[start, n]
        return sum(die_simulator_starting_at(i, n) for i in range(6)) % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @lru_cache(maxsize=None)
        def recursion(n,last,freq):
            if n == 0 : 
                return 1
            answer = 0
            for i in range(6) :
                if i == last :
                    if freq == rollMax[i] : continue
                    else :
                        answer+=recursion(n-1,last,freq+1)
                else :
                    answer+=recursion(n-1,i,1)
            return answer
        return recursion(n,-1,0)%(10**9+7)

from functools import lru_cache

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        @lru_cache(None)
        def dfs(i, r, t):
            if i == 0:
                return 1
            
            s = 0
            for k in range(6):
                if r == k:
                    if t < rollMax[k]:
                        s += dfs(i-1, r, t+1)
                else:
                    s += dfs(i-1, k, 1)
            return s
        
        return dfs(n, -1, 0) % (10 ** 9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dp[i][j][k] : ith roll, end with j with consecutive k times
        MOD = 10 ** 9 + 7
        rdim = max(rollMax)
        dp = [[[0] * rdim for _ in range(6)] for _ in range(n)]
        
        # init
        for j in range(6):
            dp[0][j][0] = 1
        
        for i in range(1, n):
            for j in range(6):
                for prev in range(6):
                    for k in range(rollMax[prev]):
                        if j == prev and k < rollMax[prev] - 1:
                            dp[i][j][k + 1] += dp[i - 1][prev][k] % MOD
                        if j != prev:
                            dp[i][j][0] += dp[i - 1][prev][k] % MOD
        
        return sum(dp[n - 1][j][k] for j in range(6) for k in range(rdim)) % MOD

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dp[i][j][k]: number of sequences end with k js when throw dice for i times
        # dp[i][*][1] = 1
        # dp[i][j][1] = sum(dp[i - 1][p][*]) j != p
        # dp[i][j][k + 1] = dp[i - 1][j][k] k < rollMax[j]
        mod = 10**9 + 7
        maxRoll = max(rollMax)
        dp = [[[0] * (maxRoll + 1) for _ in range(6)] for _ in range(n + 1)]
        for j in range(6):
            dp[1][j][1] = 1
        for i in range(2, n + 1):
            for j in range(6):
                for p in range(6):
                    for k in range(1, rollMax[p] + 1):
                        if p != j:
                            dp[i][j][1] = (dp[i][j][1] + dp[i - 1][p][k]) % mod
                        elif k < rollMax[p]:
                            dp[i][j][k + 1] = dp[i - 1][j][k]
        res = 0
        for j in range(6):
            for k in range(1, rollMax[j] + 1):
                res = (res + dp[n][j][k]) % mod
        return res

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @lru_cache(None)
        def fun(last,no,con):
            if no == n:
                return 1
            count = 0
            for i in range(6):
                if i != last:
                    count+=fun(i,no+1,1)
                elif con < rollMax[i]:
                    count += fun(i,no+1,con+1)
            return count
        ans = 0
        for i in range(6):
            ans+= fun(i,1,1)
        return ans%(10**9+7)


from functools import lru_cache 
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        #dp[idx,prev]  = (dp[idx-1,prev] +  
        @lru_cache(None)
        def helper(idx,prev):
            e,c = prev 
            if idx == n:
                return 1
            count = 0 
            for i in range(6):
                if e == i:
                    if c<rollMax[i]:
                        count += helper(idx+1,(i,c+1))% (10**9 + 7)
                else:
                    count += helper(idx+1,(i,1)) % (10**9 + 7)
            return count %  (10**9 + 7)
        return helper(0,(-1,0)) % (10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        maxAns = 10**9 + 7
        krollMax = 15
        
        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]
        # [n+1][6][15+1]
        
        for i in range(6):
            dp[1][i][1] = 1
        
        for i in range(2,n+1):
            for j in range(6):#current dice num
                for p in range(6): # previous dice num 
                    for k in range(1, krollMax+1):
                        if k>rollMax[p]: continue
                        if j != p: #different than previous dice
                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns
                        elif k<rollMax[j]:
                                dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns
        ans = 0
        for i in range(6):
            for j in range(15+1):
                ans += dp[n][i][j]
        return ans % maxAns
                            
                    
        


from functools import lru_cache
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        @lru_cache(None)
        # die value, consecutive rolls it came up, num rolls left
        def roll(val, cons, left):
            if left == 0:
                return 1
            ans = 0
            if cons < rollMax[val]:
                ans += roll(val, cons+1, left-1)
            for nval in range(6):
                if nval != val:
                    ans += roll(nval, 1, left-1)
            return ans
        
        return roll(0,0,n) % (10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        maxAns = 10**9 + 7
        krollMax = 15
        
        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]
        # [n+1][6][15+1]
        
        for i in range(6):
            dp[1][i][1] = 1
        
        for i in range(2,n+1):
            for j in range(6):#current dice num
                for p in range(6): # previous dice num 
                    for k in range(1, krollMax+1):
                        if k>rollMax[p]: continue
                        if j != p: #different than previous dice
                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns
                        elif k<rollMax[j]:
                            dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns
        ans = 0
        for i in range(6):
            for j in range(15+1):
                ans += dp[n][i][j]
        return ans % maxAns
                            
                    
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0]*n for i in range(6)]
        m = 10**9+7
        for i in range(n):
            sum_ = 0
            for j in range(6):
                sum_ += dp[j][i-1]%m
            sum_ = sum_%m
            for j in range(6):
                if i==0:
                    dp[j][i] = 1
                else:
                    if i+1<=rollMax[j]:
                        dp[j][i] = sum_
                    else:
                        s_ = 0
                        if i-rollMax[j]==0:
                            dp[j][i] = sum_ - 1
                        else:
                            for k in range(6):

                                if k!=j:
                                    s_ += dp[k][i-1-rollMax[j]]%m
                            s_ = s_%m

                            dp[j][i] =  sum_ - s_
        res = 0
        for i in range(6):
            res += dp[i][-1]%m
        #print(dp)
        return res%m

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        @lru_cache(None)
        def dfs(n, prev, consecutive):
            if n == 0:
                return 1
            
            res = 0
            
            for next_num in range(1, 7):
                if next_num == prev:
                    if consecutive < rollMax[next_num - 1]:
                        res += dfs(n - 1, prev, consecutive + 1)
                else:
                    res += dfs(n - 1, next_num, 1)
            
            return res
        
        return dfs(n, None, 0) % MOD

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10 ** 9 + 7

        @lru_cache(None)
        def dfs(i, num, k):
            if i == n:
                return 1
            ans = 0
            for j in range(6):
                if j != num:
                    ans += dfs(i + 1, j, 1)
                elif k < rollMax[j]:
                    ans += dfs(i + 1, j, k + 1)
            return ans

        ans = 0
        for i in range(6):
            ans += dfs(1, i, 1)
        return ans % mod
                    


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        M, K = 6, 15
        dp = [[[0]*(K + 1) for _ in range(M + 1)] for _ in range(n + 1)]
        
        for i in range(1, M+1):
            dp[1][i][1] = 1
            
        for i in range(2, n+1):           
            for j in range(1, M+1):  
                
                for m in range(1, M+1):
                    if m != j:
                        dp[i][j][1] += sum(dp[i-1][m][h] for h in range(1, rollMax[m-1] + 1))

                for k in range(1, K):
                    # print()
                    # print(i, j, k)
                    # print(i-j, j, k-1)
                    dp[i][j][k+1] += dp[i-1][j][k]
        
        
        # for i in range(1, n+1):
            # for j in range(1, 7):
                # print()
                # print(\"i, j: \", i, j)
                # print(\"dp[i][j]: \", dp[i][j])
                
        ans = 0
        for m in range(1, M+1):
            for k in range(1, rollMax[m-1] + 1):
                ans += dp[-1][m][k]
                
        return ans % (10**9 + 7)

class Solution:
  def dieSimulator(self, n: int, rollMax: List[int]) -> int:
    # Basic solution: 3 dimensions, n rolls, last roll, last consecutive count -> O(n^2)
    # Can we reduce to O(n) or O(nlogn)? Seems not.
    d = {}
    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.)
#       if n == 1:
#         return 1 if k == 1 else 0
#       if (n, v, k) not in d:
#         if k == 1:
#           d[(n, v, k)] = 0
#           for i, lim in enumerate(rollMax):
#             if i != v:
#               d[(n, v, k)]
#         else:
#           d[(n, v, k)] = dp(n-1, v, k-1)
      
      if n == 1:
        return 1
      if (n, v, k) not in d:
        if k == 1:
          d[(n, v, k)] = 0
          for i, lim in enumerate(rollMax):
            if i != v:
              d[(n, v, k)] += dp(n-1, i, lim) # All others
        elif k == 2:
          d[(n, v, k)] = dp(n, v, 1) + dp(n-1, v, k-1)
        else:
          # 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)
          d[(n, v, k)] = dp(n, v, k-1) + dp(n-1, v, k-1) - dp(n-1, v, k-2)
      return d[(n, v, k)]
    
    def get_exact(n, v, k):
      if k == 1:
        return dp(n, v, k)
      return dp(n, v, k) - dp(n, v, k-1)
    
    res = 0
    for i, lim in enumerate(rollMax):
      for j in range(1, lim+1):
        res += get_exact(n, i, j)

    return res % (10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @lru_cache(maxsize=None)
        def dfs(n, i, k):
            if not n: return 1
            ans = 0
            for j in range(6):
                if i != j: ans += dfs(n-1, j, 1)
                elif k+1 <= rollMax[j]: ans += dfs(n-1, j, k+1)
            return ans    
        return sum(dfs(n-1, i, 1) for i in range(6)) % 1000000007


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        #dp[i][j][k]: ith turn end with j continues number of k
        dp = [ [[0]*6 for _ in range(16)] for _ in range(n) ]
        
        #iterate the first rolling
        for k in range(6):
            dp[0][1][k] = 1
        
        mod = 10**9+7
        # iterate rest n-1 time rollings
        for i in range(1,n):
            # for this turn rolling ending with k
            for k in range(6):
                #for last turn rolling ending with prev
                for prev in range(6):
                    # for last turn ending with continous j number of prev 
                    for j in range(1,min(rollMax[prev],i+1)+1):
                        if prev == k:
                            dp[i][j][k]+=dp[i-1][j-1][k]
                            dp[i][j][k]%=mod
                        else:
                            dp[i][1][k]+=dp[i-1][j][prev]
                            dp[i][1][k]%=mod
        
        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:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        maxAns = 10**9 + 7
        krollMax = 15
        
        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]
        # [n+1][6][15+1]
        
        for i in range(6):
            dp[1][i][1] = 1
        
        for i in range(2,n+1):
            for j in range(6):#current dice num
                for p in range(6): # previous dice num 
                    for k in range(1, krollMax+1):
                        if k>rollMax[p]: continue
                        if j != p: #different than previous dice
                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns
                        elif k<rollMax[j]:
                            dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns
        ans = 0
        for i in range(6):
            for j in range(rollMax[i]+1):
                ans += dp[n][i][j]
        return ans % maxAns
                            
                    
        


import functools
class Solution:
    def dieSimulator(self, n: int, R: List[int]) -> int:
        @functools.lru_cache(None)
        def g(n,k):
            if n < 1: return 0
            if n == 1: return 1
            return f(n-1) - f(n-R[k-1]-1) + g(n-R[k-1]-1,k)

        @functools.lru_cache(None)
        def f(n):
            if n < 0 : return 0
            if n == 0 : return 1
            return sum([g(n,k) for k in range(1,7)])

        return f(n) % (10 ** 9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        #dp[i][j][k]: ith turn end with j continues number of k
        dp = [ [[0]*6 for _ in range(16)] for _ in range(n) ]
        
        #iterate the first rolling
        for k in range(6):
            dp[0][1][k] = 1
        
        mod = 10**9+7
        # iterate rest n-1 time rollings
        for i in range(1,n):
            # for this turn rolling ending with k
            for k in range(6):
                #for last turn rolling ending with prev
                for prev in range(6):
                    # for last turn ending with continous j number of prev 
                    for j in range(1,min(rollMax[prev],i+1)+1):
                        if prev == k:
                            dp[i][j][k]+=dp[i-1][j-1][k]
                            dp[i][j][k]%=mod
                        else:
                            dp[i][1][k]+=dp[i-1][j][prev]
                            dp[i][1][k]%=mod
        
        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:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = {(i, 1):1 for i in range(6)}
        for _ in range(1, n):
            dp2 = {}
            for r, t in dp:
                for i in range(6):
                    if r==i:
                        if t==rollMax[i]:
                            continue
                        else:
                            dp2[(r, t+1)] = dp[(r, t)]
                    else:
                        dp2[(i, 1)] = dp2.get((i, 1), 0)+dp[(r, t)]
            
            dp = dp2
        
        return sum(dp.values())%(10**9+7)

from functools import lru_cache
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @lru_cache(maxsize=None)
        def dfs(left, last, length):
            if left == 0:
                if length <= rollMax[last]:
                    return 1
                else:
                    return 0
            total = 0
            for i in range(6):
                if i == last:
                    if length + 1 <= rollMax[last]:
                        total += dfs(left - 1, i, length + 1)
                else:
                    total += dfs(left - 1, i, 1)
            return total
        
        return dfs(n, -1, 0) % (10 ** 9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @lru_cache(maxsize=None)
        def dfs(n, i, k):
            if not n: return 1
            ans = 0
            for j in range(6):
                if i != j: 
                    ans += dfs(n-1, j, 1)
                elif k+1 <= rollMax[j]: 
                    ans += dfs(n-1, j, k+1)
                    
            return ans    
        
        ans = sum(dfs(n-1, i, 1) for i in range(6))
        
        return ans % 1000000007
    
    
    
    # https://leetcode.com/problems/dice-roll-simulation/discuss/833495/Python-3-or-DFS-%2B-Memoization-or-Explanation


from functools import lru_cache
class Solution:
   
    @staticmethod
    def ans_mod(n):
        return n % (10**9 + 7)
    
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # so we need to think about 
    
        @lru_cache(None)
        def roll(val, consec_rolls, rolls_left):
            if rolls_left == 0:
                return 1
            
            ans = 0
            
            if consec_rolls < rollMax[val]:
                ans += roll(val, consec_rolls +1, rolls_left - 1)
            
            # now we consider all other possible rolls but not the same val
            for i in range(6):
                if i == val:
                    continue
                ans += roll(i, 1, rolls_left - 1)
            return ans
    
        return self.ans_mod(roll(0, 0, n))
            


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        maxAns = 10**9 + 7
        krollMax = 15
        
        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]
        # [n+1][6][15+1]
        
        for i in range(6):
            dp[1][i][1] = 1
        
        for i in range(2,n+1):
            for j in range(6):#current dice num
                for p in range(6): # previous dice num 
                    for k in range(1, krollMax+1):
                        if j != p: #different than previous dice
                            if k>rollMax[p]: continue
                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns
                        elif k<rollMax[j]:
                                dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns
        ans = 0
        for i in range(6):
            for j in range(15+1):
                ans += dp[n][i][j]
        return ans % maxAns
                            
                    
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        maxAns = 10**9 + 7
        krollMax = 15
        
        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]
        # [n+1][6][15+1]
        
        for i in range(6):
            dp[1][i][1] = 1
        
        for i in range(2,n+1):
            for j in range(6):#current dice num
                for p in range(6): # previous dice num 
                    for k in range(1, krollMax+1):
                        if j != p: #different than previous dice
                            if k>rollMax[p]: continue
                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns
                        else:
                            if k<rollMax[j]:
                                dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns
        ans = 0
        for i in range(6):
            for j in range(15+1):
                ans += dp[n][i][j]
        return ans % maxAns
                            
                    
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        @lru_cache(maxsize=None)
        
        def dfs(n, i, k):
            if not n: 
                return 1
            ans = 0
            for j in range(6):
                if i != j:
                    ans += dfs(n-1, j, 1)
                elif k+1 <= rollMax[j]:
                    ans += dfs(n-1, j, k+1)
            return ans
        
        return sum(dfs(n-1, i, 1) for i in range(6)) % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        @lru_cache(None)
        def dp(pos, last, numlast):
            if pos == n:
                return 1
            
            res = 0
            
            for i in range(1,7):
                if i != last:
                    res += dp(pos+1, i, 1)
                elif numlast < rollMax[i-1]:
                    res += dp(pos+1, last, numlast+1)
            
            return res
        
        return dp(0,0,0) % (10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @lru_cache(maxsize=None)
        def dfs(n, i, k):
            if not n: return 1
            ans = 0
            for j in range(6):
                if i != j:
                    ans += dfs(n-1, j, 1)
                elif k+1 <= rollMax[j]:
                    ans += dfs(n-1, j, k+1)
            return ans    
        
        return sum(dfs(n-1, i, 1) for i in range(6)) % 1000000007

class Solution:
    def dieSimulator(self, n: int, roll_max: List[int]) -> int:
        
        
        
        dices = defaultdict(int, {(-1, 0) : 1}) # previous n, # of consecutive : ways
        for _ in range(n):
        
            prev_dices = tuple(dices.items())
            dices.clear()
            
            for pc, ways in prev_dices:
                prev, consecutive = pc
                for r, r_max in enumerate(roll_max):
                    c = int(r == prev) * consecutive + 1
                    if c <= r_max:
                        dices[r, c] += ways
            
        return sum(dices.values()) % (10 ** 9 + 7)

def dfs(curr_index, n, rollMax, prev, d):
        if curr_index == n:
            return 1
        if curr_index > n:
            return 0
        if (curr_index, prev) in d:
            return d[(curr_index, prev)]
        count = 0
        for i in range(6):
            if i!=prev:
                for repeat in range(1, rollMax[i]+1):
                    count+=dfs(curr_index+repeat, n, rollMax, i, d)
            d[(curr_index,prev)] = count
                
        return count
    
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        d = {}
        MOD = 1000000007
        return dfs(0, n, rollMax, -1,d)%MOD

class Solution:
    def dieSimulator(self, n: int, roll_max: List[int]) -> int:
        @lru_cache(maxsize=None)
        def die_simulator(n, consec_num, consec_count):
            if n == 0:
                return 1
            else:
                res = 0
                for i in range(6):
                    if i == consec_num:
                        if roll_max[i] > consec_count:
                            res += die_simulator(n - 1, i, consec_count + 1)
                    elif roll_max[i] != 0:
                        res += die_simulator(n - 1, i, 1)
                return res
                
        return die_simulator(n, -1, 0) % (10 ** 9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        def ways(side, already, rolls, mem):
            key = (side, already, rolls)
            if key in mem: return mem[key]
            
            if already >= rollMax[side]:
                mem[key] = 0
                return 0

            if rolls == 0:
                mem[key] = 1
                return 1
            
            ans = 0
            ans += ways(side, already+1, rolls-1, mem)
            for i in range(6):
                if i == side: continue
                ans += ways(i, 0, rolls-1, mem)

            mem[key] = ans % (10 ** 9 + 7)
            return mem[key]
            
        ans = 0
        mem = {}
        for i in range(6):
            ans += ways(i, 0, n-1, mem)
        return ans % (10 ** 9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = {(i, 1): 1 for i in range(6)}
        for i in range(n - 1):
            next_dp = collections.Counter()
            for (d, c), v in list(dp.items()):
                for cur in range(6):
                    if cur != d:
                        next_dp[(cur, 1)] += v
                    else:
                        if c + 1 <= rollMax[cur]:
                            next_dp[(cur, c + 1)] += v
            dp = next_dp
        
        return sum(dp.values()) % (10 ** 9 + 7)
#         def dfs(m, k, con):
#             if m == 1: return 1, 1
#             res = [0, 1]
#             for i in range(6):
#                 total, con = dfs(m - 1, i)
#                 if k == i:
#                     if con + 1 <= rollMax[i - 1]:
#                         res[0] += total
#                         res[1] = con + 1
#                 else:
#                     res += total
        
#         return sum(dfs(n, i) for i in range(6)) % (10 ** 9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        @lru_cache(maxsize=None)
        def dfs(c,l,d):
            nonlocal n
            nonlocal rollMax
            
            
            if rollMax[l] < d:
                return 0
            
            if c == n:
                return 1
            
            sm = 0
            
            for i in range(0,6):
                sm += dfs(c+1,i,1+d*(i==l))
                    
            
            return sm
        
        return dfs(0,-1,0)%(10**9 +7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        def helper(currentIndex, n, rollMax, pre,d):
            if currentIndex==n:
                return 1
            elif currentIndex>n:
                return 0
            count = 0
            if (currentIndex,pre) in d: #if this state is already calculated, return the ans
                return d[(currentIndex,pre)]
            for index in range(6):
                if index!=pre:
                    for repeat in range(1,rollMax[index]+1):
                        count+=helper(currentIndex+repeat,n,rollMax,index,d)
            d[(currentIndex,pre)]=count   #save the computation
            return count
        
        rolledCount = [0]*6  #no rolls made yet
        MOD = 10**9+7
        d = {}  #dictionary to save the states
        return helper(0,n,rollMax,-1,d)%MOD
    

        
        
#         memo = {}
#         def dfs(last, s,  k):
#             if k == n:
#                 return 1
#             if (last, s, k) not in memo:
#                 res = 0
#                 for i in range(6):
#                     if i == last:
#                         if s + 1 > rollMax[i]:
#                             continue
#                         else:
#                             res += dfs(i, s+1, k+1)
#                     else:
#                         res += dfs(i, 1, k+1)
#                 memo[last, s, k] = res
#             return memo[last, s, k]
        
        
#         return dfs(None, 0, 0)%(10**9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = {(i, 1): 1 for i in range(6)}
        for i in range(n - 1):
            next_dp = collections.Counter()
            for (d, c), v in list(dp.items()):
                for cur in range(6):
                    if cur != d:
                        next_dp[(cur, 1)] += v
                    else:
                        if c + 1 <= rollMax[cur]:
                            next_dp[(cur, c + 1)] += v
            dp = next_dp
        return sum(dp.values()) % (10 ** 9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        maxAns = 10**9 + 7
        krollMax = 15
        
        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]
        # [n+1][6][15+1]
        
        for i in range(6):
            dp[1][i][1] = 1
        
        for i in range(2,n+1):
            for j in range(6):#current dice num
                for p in range(6): # previous dice num 
                    for k in range(1, krollMax+1):
                        if k>rollMax[p]: continue
                        if j != p: #different than previous dice
                            dp[i][j][1] = dp[i][j][1] + dp[i-1][p][k]
                        elif k<rollMax[j]:
                                dp[i][j][k+1] = dp[i][j][k+1] + dp[i-1][p][k]
                                # dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns
        ans = 0
        for i in range(6):
            for j in range(15+1):
                ans += dp[n][i][j]
        return ans % maxAns
                            
                    
        


import functools as ft


class Solution:
    
    BASE = 10 ** 9 + 7
    
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.roll_max = rollMax
        return self.count(n, 1, 0)
    
    @ft.lru_cache(None)
    def count(self, remaining: int, last_roll: int, streak: int) -> int:
        if remaining == 0:
            return 1
        ans = 0
        for dice in range(1, 7):
            if dice == last_roll:
                if streak >= self.roll_max[last_roll - 1]:
                    continue
                ans += self.count(remaining - 1, dice, streak + 1)
            else:
                ans += self.count(remaining - 1, dice, 1)
        return ans % self.BASE

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dp[i][j][k] : ith roll, end with j with consecutive k times
        MOD = 10 ** 9 + 7
        rdim = max(rollMax)
        dp = [[[0] * rdim for _ in range(6)] for _ in range(n)]
        
        # init
        for j in range(6):
            dp[0][j][0] = 1
        
        for i in range(1, n):
            for j in range(6):
                for prev in range(6):
                    for k in range(min(rollMax[prev], i + 1)):
                        if j == prev and k < rollMax[prev] - 1:
                            dp[i][j][k + 1] += dp[i - 1][prev][k] % MOD
                        if j != prev:
                            dp[i][j][0] += dp[i - 1][prev][k] % MOD
        
        return sum(dp[n - 1][j][k] for j in range(6) for k in range(rdim)) % MOD

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10**9 + 7
        memoi = [[1] + ([0] * (limit - 1)) for limit in rollMax]
        for _ in range(1, n):
            sumVal = sum(map(sum, memoi)) % MOD
            newMemoi = []
            for face in range(1, 7):
                limits = []
                limits.append((sumVal - sum(memoi[face-1])) % MOD)
                for limit in range(1, rollMax[face-1]):
                    limits.append(memoi[face-1][limit-1])
                newMemoi.append(limits)
            memoi = newMemoi
        return sum(map(sum, memoi)) % MOD


class Solution:
    def dieSimulator(self, n: int, R: List[int]) -> int:
        D, R, S, m = [[0]*7 for _ in range(n)], [0]+R, set(range(1,7)), 10**9 + 7
        def dfs(L, d):
            if L >= n: return 1 if L == n else 0
            c = 0
            if D[L][d]: return D[L][d]
            for i in S-{d}:
                for j in range(1,R[i]+1): c += dfs(L+j,i)
            D[L][d] = c
            return c
        return dfs(0,0) % m

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        max_num = max(rollMax)
        dp = [[[0]*(max_num+1) for _ in range(6)] for _ in range(n+1)]
        for j in range(6):
            dp[1][j][1] = 1
        for i in range(2,n+1):
            for j in range(6):
                for p in range(6):
                    for k in range(1,max_num+1):
                        if p != j:
                            dp[i][j][1] = (dp[i][j][1] + dp[i - 1][p][k])%(10**9+7)
                        elif k < rollMax[p]:
                            dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i - 1][p][k])%(10**9+7)
        ans = 0
        for j in range(6):
            for k in range(1,max_num+1):
                ans = (ans + dp[n][j][k])%(10**9+7)
        return ans


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        cach = {}
        def helper(remain,last,rollMax):    
            if (remain,last) in cach:
                return cach[(remain,last)]
            else:
                if remain==0:
                    return 1
                else:
                    ret = 0
                    for i in range(6):
                        if last==i:    
                            continue
                        else:
                            for j in range(rollMax[i]):
                                if remain-j-1>=0:
                                    ret += helper(remain-j-1,i,rollMax)
                cach[(remain,last)] = ret%1000000007
                return cach[(remain,last)]
        return helper(n,-1,rollMax)


class Solution:
    
        
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        memo = [[[0 for k in range(16)] for j in range(7)] for i in range(n+1)]
        result = 0
        mod = 10 ** 9 + 7 
        
        
        def dfs(n, index, k):
            if n == 0:
                return 1
            if memo[n][index][k] != 0:
                return memo[n][index][k]
            result = 0
            for i in range(6):
                if i == index:
                    if rollMax[i] > k:
                        result += dfs(n-1, i, k+1)
                else:
                    result += dfs(n-1, i, 1)
                    result %= mod
            memo[n][index][k] = result % mod
            return memo[n][index][k]
        
        
        
        
        
        
        
        
        
        
        for i in range(6):
            result += dfs(n-1, i, 1)
            result %= mod
        return result % mod 
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
      @lru_cache(None)
      def count(n,idxCnt):
        if not n: return 1
        idx,cnt = idxCnt
        out = 0
        for i in range(6):
          times = rollMax[i]
          if idx == i:
            if times >cnt:
              out+=count(n-1,(i,cnt+1))
          else:      
              out+=count(n-1,(i,1))
        return out 
      return count(n, (0,0))%1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @lru_cache(None)
        def helper(n, consec):
            # consec: [0,2] already roll 1 twice
            if rollMax[consec[0]] < consec[1]:
                return 0
            elif n == 0:
                return 1

            res = []
            for i in range(1, 7):
                if i - 1 ==  consec[0]:
                    res.append(helper(n-1, (consec[0], consec[1] + 1)))
                else:
                    res.append(helper(n-1, (i-1, 1)))
            # print(n , res, sum(res), sum(res) % (10**9+7))
            return sum(res) % (10**9+7)
        
        return helper(n, (0,0))


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        if n < 1:
            return 0
        
        def backtrack(prev_roll, count, seq_len):
            if seq_len == n:
                return 1
            
            if (prev_roll, count, seq_len) in cache:
                return cache[(prev_roll, count, seq_len)]
            result = 0

            for num in range(6):
                if num != prev_roll:
                    result += backtrack(num, 1, seq_len+1)
                elif count < rollMax[num]:
                    result += backtrack(num, count+1, seq_len+1)
            
            cache[(prev_roll, count, seq_len)] = result % MOD
            return cache[(prev_roll, count, seq_len)]
        
        MOD = (10 ** 9) + 7
        cache = {}
        return backtrack(-1, 0, 0)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        modVal = 10**9 + 7
        memo = {}
        def recurse(numLeft, prevNum, prevNumCount):
            if numLeft == 0:
                return 1
            
            if (numLeft, prevNum, prevNumCount) in memo:
                return memo[(numLeft, prevNum, prevNumCount)]
            
            numWays = 0
            for i in range(len(rollMax)):
                if i == prevNum:
                    if prevNumCount < rollMax[i]:
                        numWays += recurse(numLeft - 1, i, prevNumCount + 1)
                else:
                    numWays += recurse(numLeft - 1, i, 1)
            
            memo[(numLeft, prevNum, prevNumCount)] = numWays % modVal
            
            return numWays
        
        return recurse(n, -1, -1) % modVal

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        memo, mod = [[0]*6 for _ in range(n)], 10**9+7
        memo[0] = [1]*6
        
        for i in range(1,n):
            prev_sum = sum(memo[i-1]) % mod
            for j in range(6):
                memo[i][j] = prev_sum
                if i == rollMax[j]:
                    memo[i][j] -= 1
                elif i > rollMax[j]:
                    memo[i][j] = (memo[i][j] - sum(memo[i-rollMax[j]-1]) + memo[i-rollMax[j]-1][j]) % mod
                
        return sum(memo[n-1]) % mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]
        for j in range(len(rollMax)):
            dp[1][j] = 1
            dp[1][-1] += dp[1][j]
        
        for i in range(2, n + 1):
            for j in range(len(rollMax)):
                dp[i][j] = dp[i - 1][-1]
                k = i - rollMax[j]
                if k == 1:
                    dp[i][j] -= 1
                elif k > 1:
                    dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])
                dp[i][-1] += dp[i][j]
        return dp[n][-1] % int(1e9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        def solve(i, numConsecutive, last):
            # Base case: finished one iteration
            if i == n:
                return 1
            
            # Memoization case
            if (i, numConsecutive, last) in memo:
                return memo[(i, numConsecutive, last)]
            
            # Recursive cases: try every roll as long as it doesn't interfere
            count = 0
            
            for f in range(6):
                if last != f:
                    count += solve(i+1, 1, f)
                
                elif numConsecutive + 1 <= rollMax[f]:
                    count += solve(i+1, numConsecutive + 1, last)
            
            count %= MOD
            memo[(i, numConsecutive, last)] = count
            return count
        
        MOD = 10**9 + 7
        memo = {}
        return solve(0, 0, -1)

from functools import lru_cache
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        @lru_cache(None)
        def roll(val, cons, left):
            if left == 0: return 1
            
            ans = sum([roll(nval, 1, left-1) for nval in range(6) if nval != val])
            
            if cons < rollMax[val]:
                ans += roll(val, cons+1, left-1)
                
            return ans
        
        return roll(0,0,n) % (10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        mem={}
        mod=int(10**9)+7
        
        def rec(n,li,k):
            if n==0:
                return 1
            elif (n,li,k) in mem:
                return mem[(n,li,k)]
            else:
                ans=0
                for i in range(6):
                    if i==li:
                        if k+1<=rollMax[li]:
                            ans+=rec(n-1,li,k+1)%mod
                    else:
                        ans+=rec(n-1,i,1)%mod
                mem[(n,li,k)]=ans%mod
                return ans%mod
            
        
        return rec(n,0,0)%mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        def helper(last,index,maxval):
            if index==n:
                return 1
            
            val=0
            
            if (index,last,maxval) in dp:
                return dp[(index,last,maxval)]
            for i in range(6):
                if last==i:
                    if maxval+1>rollMax[i]:
                        continue
                    else:
                        val+=helper(i,index+1,maxval+1)
                else:
                    val+=helper(i,index+1,1)
            dp[(index,last,maxval)]= val %(10**9 + 7)
            return val
            
            
        dp={}
        return helper(None,0,0)%(10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10**9+7
        dp = {}
        
        def helper(preV, repeat, n0):
            if n0 == 0:
                return 1
            if (preV, repeat, n0) in dp:
                return dp[(preV, repeat, n0)]
            
            subAns = 0
            for nextV in range(1, 7):
                if nextV == preV:
                    if repeat < rollMax[preV-1]:
                        subAns += helper(preV, repeat+1, n0-1)
                else:
                    subAns += helper(nextV, 1, n0-1)
            dp[(preV, repeat, n0)] = subAns % MOD
            return dp[(preV, repeat, n0)]
        return helper(-1, 0, n)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10**9+7
        dp = {}
        
        def helper(preV, repeat, n0):
            if n0 == 0:
                return 1
            if (preV, repeat, n0) in dp:
                return dp[(preV, repeat, n0)]
            
            subAns = 0
            for nextV in range(1, 7):
                if nextV == preV:
                    if repeat < rollMax[preV-1]:
                        subAns += helper(preV, repeat+1, n0-1)
                else:
                    subAns += helper(nextV, 1, n0-1)
            dp[(preV, repeat, n0)] = subAns % MOD
            return dp[(preV, repeat, n0)]
        return helper(-1, 0, n) % MOD

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        memo = {}
        def dfs(last, s,  k):
            if k == n:
                return 1
            if (last, s, k) not in memo:
                res = 0
                for i in range(6):
                    if i == last:
                        if s + 1 > rollMax[i]:
                            continue
                        else:
                            res += dfs(i, s+1, k+1)
                    else:
                        res += dfs(i, 1, k+1)
                memo[last, s, k] = res%(10**9 + 7)
            return memo[last, s, k]
        return dfs(None, 0, 0)%(10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0 for _ in range(len(rollMax)+1)] for _ in range(n+1)]
        for j in range(len(rollMax)):
            dp[1][j] = 1
            dp[1][-1] += dp[1][j]
        for i in range(2,n+1):
            for j in range(len(rollMax)):
                dp[i][j] = dp[i-1][-1]
                k = i - rollMax[j]
                if k == 1:
                    dp[i][j] -= 1
                elif k > 1:
                    dp[i][j] -= (dp[k-1][-1] - dp[k-1][j])
                dp[i][-1] += dp[i][j]
        return dp[-1][-1] % int(1e9+7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dp template 2: number of paths
        
        
        cache = {}
        MOD = 10**9 + 7
        def dp(n: int, prev_roll: int, prev_count: int) -> int:
            if n == 0:
                return 1
            
            if (n, prev_roll, prev_count) in cache: # store state
                return cache[n, prev_roll, prev_count]
            
            res = 0
            for i in range(len(rollMax)):
                if prev_roll != None and i == prev_roll:
                    if prev_count == rollMax[i]: # can't be more than rollMax[i] consecutive times
                        continue
                    res += dp(n-1, i, prev_count+1)
                else:
                    res += dp(n-1, i, 1)
            
            cache[n, prev_roll, prev_count] = res % MOD
            return res % MOD
        
        return dp(n, None, None)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        def roll(last,last_num,rolls):
            if rolls==0:
                return 1
            if (last,last_num,rolls) in memo:
                return memo[(last,last_num,rolls)]
            tmp = 0
            for cur in range(1,7):
                if cur==last:
                    if last_num+1>rollMax[cur-1]:
                        continue
                    tmp += roll(last,last_num+1,rolls-1)
                else:
                    tmp += roll(cur,1,rolls-1)
                tmp = tmp % (10**9 +7)
            memo[(last,last_num,rolls)] = tmp
            return tmp
        
        
        memo = {}
        return roll(-1,0,n)
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        memo = {}
        def dfs(last, s,  k):
            if k == n:
                return 1
            if (last, s, k) not in memo:
                res = 0
                for i in range(6):
                    if i == last:
                        if s + 1 > rollMax[i]:
                            continue
                        else:
                            res += dfs(i, s+1, k+1)
                    else:
                        res += dfs(i, 1, k+1)
                memo[last, s, k] = res%(10**9 + 7)
            return memo[last, s, k]
        return dfs(None, 0, 0)%(10**9 + 7)


class Solution:
    def dieSimulatorLast(self, n, rollMax, last, count):
        # n: number of rolls
        # rollMax: 
        # last: the last number in the sequence
        # count: how many times `last` occurs consecutively in the sequence
        if count > rollMax[last]:
            return 0
        elif n == 0:
            return 1
        elif self.result[last][count][n] != -1:
            return self.result[last][count][n]
        
        temp = 0
        for i in range(6):
            if i == last:
                temp += self.dieSimulatorLast(n-1,rollMax,i,count+1)
            else:
                temp += self.dieSimulatorLast(n-1,rollMax,i,1)
        self.result[last][count][n] = temp % 1000000007
                
        return temp % 1000000007
        
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.result = [[[-1 for i in range(n+1)] for j in range(17)] for k in range(6)]
        return self.dieSimulatorLast(n, rollMax, 0, 0)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[[0] * (max(rollMax)+1) for x in range(7)] for x in range(n+1)]
        
        
        def dfs(roll,prev,count):
            
            if roll == 0:
                return 1
            
            if dp[roll][prev][count] != 0:
                return dp[roll][prev][count]
            
            result = 0
            for x in range(1,7):
                if x == prev:
                    if count < rollMax[x-1]:
                        result += dfs(roll-1,x,count+1)
                else:
                    result += dfs(roll-1,x,1)
            
            dp[roll][prev][count] = result
            return result
    
        return dfs(n,0,0) % 1000000007

def simulatorHelper(n, rollMax, consec, rolls, last, dp):
    if rolls == n:
        return 1
    elif dp[rollMax[last]][consec][rolls] != -1:
        return dp[rollMax[last]][consec][rolls]
    else:
        total = 0
        for i in range(len(rollMax)):
            if last == i and consec == rollMax[i]:
                continue
            else:
                if last == i:
                    total += simulatorHelper(n, rollMax, consec + 1, rolls + 1, i, dp)
                else:
                    total += simulatorHelper(n, rollMax, 1, rolls + 1, i, dp)
        dp[rollMax[last]][consec][rolls] = total
        return total
def simulator(n, rollMax):
    dp = [[[-1 for rolls in range(n + 1)] for consec in range(16)] for rollMax in range(16)]
    return simulatorHelper(n, rollMax, 0, 0, 0, dp) % (10 ** 9 + 7)

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

#[Runtime: 864 ms, faster than 53.84%] DP(bottom-up)
#O(6N * 6T): T: upperbound of rollMax

#f(i, d): number of combinations of res[0~i] if the last number is d
#f(0, ?) = 1
#                 |------------| <= rollMax[d]
#               d'd d d ... d [d]
#               ? d'd d ... d [d]
#               ? ? d'd ... d [d]
#               ? ? ? d'... d [d]
#               ? ? ? ? ... d'[d]
#f(i, d) = sum{ f(j, d') for j in i-rollMax[d] ~ i-1 for d' in 0~5
#               if i-rollMax[d] >= 0 and d' != d }
#          sum{ f(i-1, d') for any d' if i < rollMax[d]} < no limit
#or
#total(i) = sum(f(i, d) for d in range(6))
#f(i, d) = sum( total[j] - f(j, d) for j in i-rollMax[d]~i-1 ) if i >= rollMax[d]
#          total[i-1] if i < rollMax[d]
MOD = 1000000007
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * 6 for _ in range(n)]
        total = [0] * n
        for d in range(6):
            dp[0][d] = 1
        total[0] = sum(dp[0][d] for d in range(6))
        for i in range(1, n):
            for d in range(6):
                if i < rollMax[d]: #no constraint
                    dp[i][d] = total[i-1]
                else:
                    dp[i][d] = sum(total[j] - dp[j][d] for j in range(i-rollMax[d], i)) % MOD
            total[i] = sum(dp[i][d] for d in range(6)) % MOD
        return total[n-1]

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        maxAns = 10**9 + 7
        krollMax = 15
        
        dp = [[[0]*(krollMax+1) for i in range(6)] for j in range(n+1)]
        # [n+1][6][15+1]
        
        for i in range(6):
            dp[1][i][1] = 1
        
        for i in range(2,n+1):
            for j in range(6):#current dice num
                for p in range(6): # previous dice num 
                    for k in range(1, krollMax+1):
                        if j != p: #different than previous dice
                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][p][k])%maxAns
                        else:
                            if k<rollMax[j]:
                                dp[i][j][k+1] = (dp[i][j][k+1] + dp[i-1][p][k])%maxAns
        ans = 0
        for i in range(6):
            for j in range(15+1):
                ans += dp[n][i][j]
        return ans % maxAns
                            
                    
        


class Solution:
    def dieSimulator(self,n, rollMax):
        if n==1:
            return 6
        mod = int(1e9+7)
        #naive dp
        dp = [[[0]*15 for j in range(6)] for i in range(n)]
        #print(len(dp))
        #init
        for i in range(6):
            dp[0][i][0] = 1
        #main process
        for i in range(1,n):
            for p in range(6):
                for j in range(6):
                    for k in range(15):
                        #update dp[i][j][0]
                        if p!=j:
                            dp[i][j][0] = (dp[i][j][0]+dp[i-1][p][k]) % mod
                        #update dp[i][j][k]
                        elif k>0 and k<rollMax[j]:
                            dp[i][j][k] = dp[i-1][j][k-1]
        ans = 0
        for j in range(6):
            for k in range(15):
                ans = (ans + dp[-1][j][k]) % mod
        return ans


class Solution:
    # @lru_cache(None)
    def __init__(self):
        self.store = defaultdict(int)
    def rds(self, n, rm, pre, prec):
        if n==0:
            return 1
        else:
            if (n, pre, prec) in self.store:
                return self.store[(n, pre, prec)]
            else:
                result = 0
                for i in range(6):
                    if i==pre:
                        if prec<rm[i]:
                            result+=self.rds(n-1, rm, i, prec+1)
                    else:
                        result+=self.rds(n-1, rm, i, 1)
                result%=1000000007
                self.store[(n, pre, prec)] = result
                return result
    def dieSimulator(self, n: int, rm: List[int]) -> int:
        res=self.rds(n, rm, None, 0)
        return res
                    


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        cache = {}
        
        def dfs(rem, last, lastLen):
            if rem == 0:
                return 1
            
            if (rem, last, lastLen) in cache:
                return cache[(rem, last, lastLen)]
            
            ans = 0
            for i in range(1, 7):
                if i == last and lastLen == rollMax[i-1]:
                    continue
                ans = (ans + dfs(rem - 1, i, 1 if i != last else lastLen + 1)) % 1000000007
            if last != -1:
                cache[(rem, last, lastLen)] = ans
            
            return ans
        
        return dfs(n, -1, 0)

class Solution:
    # @lru_cache(None)
    def __init__(self):
        self.store = defaultdict(int)
    def rds(self, n, rm, pre, prec):
        if n==0:
            return 1
        else:
            if (n, pre, prec) in self.store:
                return self.store[(n, pre, prec)]
            else:
                result = 0
                for i in range(6):
                    if i==pre:
                        if prec<rm[i]:
                            result+=self.rds(n-1, rm, i, prec+1)
                    else:
                        result+=self.rds(n-1, rm, i, 1)
                result%=1000000007
                self.store[(n, pre, prec)] = result
                return result
    def dieSimulator(self, n: int, rm: List[int]) -> int:
        # print(rm)
        res=self.rds(n, rm, None, 0)
        return res
                    


class Solution:
    def __init__(self):
        self.store = defaultdict(int)
        
    def rds(self, n, rm, pre, prec):
        if n==0:
            return 1
        else:
            if (n, pre, prec) in self.store:
                return self.store[(n, pre, prec)]
            else:
                result = 0
                for i in range(6):
                    if i==pre:
                        if prec<rm[i]:
                            result+=self.rds(n-1, rm, i, prec+1)
                    else:
                        result+=self.rds(n-1, rm, i, 1)
                result%=1000000007
                self.store[(n, pre, prec)] = result
                return result
    def dieSimulator(self, n: int, rm: List[int]) -> int:
        res=self.rds(n, rm, None, 0)
        return res
                    


class Solution:
    # @lru_cache(None)
    def __init__(self):
        self.store = defaultdict(int)
    def rds(self, n, rm, pre, prec):
        if n==0:
            return 1
        else:
            if (n, pre, prec) in self.store:
                return self.store[(n, pre, prec)]
            else:
                result = 0
                for i in range(6):
                    if i==pre:
                        if prec<rm[i]:
                            result+=self.rds(n-1, rm, i, prec+1)
                    else:
                        result+=self.rds(n-1, rm, i, 1)
                result%=1000000007
                self.store[(n, pre, prec)] = result
                return result
    def dieSimulator(self, n: int, rm: List[int]) -> int:
        # print(rm)
        
        res = 0
        for i in range(6):
            res+=self.rds(n-1, rm, i, 1)
        return res%1000000007
                    


from functools import lru_cache

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.rollMax = rollMax
        return self.solve(n, -1, 0) % (1000000007)
        
    @lru_cache(maxsize=4096, typed=False)
    def solve(self, n, last_index=-1, last_times=0):
        if n == 0:
            return 1
        else:
            res = 0
            for i in range(6):
                if i == last_index and self.rollMax[i] > last_times:
                    res += self.solve(n - 1, i, last_times + 1)
                elif i != last_index:
                    res += self.solve(n - 1, i, 1)

            return res


class Solution:
    base = 10**9+7
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[1] * rollMax[i] for i in range(6)]
        
        for m in range(1, n):
            s = sum(dp[k][-1] for k in range(6))
            zero = [s-dp[k][-1] for k in range(6)]
            
            for i in range(6):
                for j in range(rollMax[i]-1,0,-1):
                    dp[i][j] = (zero[i] + dp[i][j-1]) % self.base
                dp[i][0] = zero[i] % self.base
        
        return sum(dp[i][-1] for i in range(6)) % self.base


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        
        return self.recur(n,-1,1,rollMax,{}) % (10**9 + 7)
        
        
    
    def recur(self,n,prev,count,rollMax,op):
        
        if (n,prev,count) in op:
            return op[(n,prev,count)]
        
        if n == 0:
            return 1 
        else:
            
            t = 0
            for i in range(6):
                
                if prev == i:
                    if count+1 <= rollMax[i]:
                        t += self.recur(n-1,i,count+1,rollMax,op)
                        
                else:
                    
                    t += self.recur(n-1,i,1,rollMax,op)
            
            op[(n,prev,count)] = t
            return t 
                    
                    


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        for i in range(len(rollMax)):
            rollMax[i] = min(rollMax[i], n)
        dp = []
        max_roll = max(rollMax) + 1
        for k in range(n + 1):
            dp.append([])
            for i in range(6):
                dp[-1].append([])
                for j in range(max_roll):
                    if k == 1 and j > 0:
                        dp[-1][-1].append(1)
                    else:
                        dp[-1][-1].append(0)

        MOD = (10 ** 9) + 7
        for k in range(1, n + 1):
            for prev_roll in range(6):
                for cur_roll in range(6):
                    for j in range(1, max_roll):
                        if prev_roll == cur_roll:
                            dp[k][prev_roll][j] += dp[k - 1][prev_roll][j - 1] % MOD
                        else:
                            dp[k][prev_roll][j] += dp[k - 1][cur_roll][rollMax[cur_roll]] % MOD
        ans = 0
        for i in range(6):
            ans += dp[n][i][rollMax[i]] % MOD
        return ans % MOD


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        
        self.mem = {}
        def dfs(length, lastnum, lastcount):
            if length==n:
                return 1
            if (length,lastnum,lastcount) in self.mem:
                return self.mem[(length,lastnum,lastcount)]
            counts = 0
            
            for i,nxt in enumerate('123456'):
                if lastnum==nxt:
                    if lastcount<rollMax[i]:
                        counts+=dfs(length+1, nxt, lastcount+1)
                else:
                    counts+= dfs(length+1,nxt,1)
                    
            counts = counts%(10**9+7)
            self.mem[(length,lastnum,lastcount)] = counts
            return counts
        
        lastnum = '0'
        lastcount=0
        res = dfs(0,'0',0)
        
        return res

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dp[i][j][k] means this is ith roll and we end up with number j and it has lasted k times
        dp = [[[0 for k in range(16)] for j in range(7)] for i in range(n + 1)]
        mod = pow(10, 9) + 7
        
        for j in range(1, 7):
            dp[1][j][1] = 1
        
        for i in range(2, n + 1):
            for j in range(1, 7):
                for k in range(1, 16):
                    if k != 1:
                        if k <= rollMax[j - 1]:
                            dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % mod
                    else:
                        for jj in range(1, 7):
                            if jj != j:
                                for kk in range(16):
                                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][jj][kk]) % mod
        
        ans = 0
        for j in range(1, 7):
            for k in range(1, 16):
                ans = (ans + dp[n][j][k]) % mod
        
        return ans

class Solution:
    @lru_cache(maxsize = None)
    def roll(self, val, consec, left):
        if left == 0:
            return 1
        
        total = 0
        
        for i in range(0,6):
            if i != val:
                total += self.roll(i, 1, left-1)
                
        if consec < self.rm[val]:
            total += self.roll(val, consec+1, left-1)
            
        return total
    
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.rm = rollMax
        
        return self.roll(0,0,n) % ((10**9) + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
             dp={}
             def die(n,i,c):
                    if n==0:
                        return 1
                    if (n,i,c) in dp:
                        return dp[(n,i,c)]
                    res=0 
                    for j in range(6):
                        if i!=j:
                            res+=die(n-1,j,1)
                        elif c<rollMax[j]:
                                res+=die(n-1,j,c+1)
                    dp[(n,i,c)]=res
                    return res 
             return die(n,-1,0)%int(1e9+7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10**9 + 7
        memoi = {}
        def numbers(n, prev, prevCount):
            if n == 0: return 1
            if (n, prev, prevCount) in memoi: 
                return memoi[n, prev, prevCount]
            res = 0
            for face in range(1, 7):
                if face != prev or rollMax[face-1] > prevCount:
                    res = (res + numbers(n - 1, face, prevCount * (face == prev) + 1)) % MOD
            memoi[n, prev, prevCount] = res
            return res
        return numbers(n, -1, 0)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[[0 for _ in range(16)] for _ in range(7)] for _ in range(n+1)]
        mod = 10**9+7

        for i in range(1, n+1):
            for j in range(1, 7):# 投掷的数
                if(i == 1):# 第一次投掷
                    dp[i][j][1] = 1
                    continue

                # 数字 j 连续出现 k 次
                for k in range(2, rollMax[j-1]+1):
                    dp[i][j][k] = dp[i-1][j][k-1]
                
                # 前一次投出的数不是 j
                temp = 0
                for l in range(1, 7):
                    if(l == j):
                        continue
                    for k in range(1, 16):
                        temp += dp[i-1][l][k]
                        temp %= mod
                dp[i][j][1] = temp
        
        res = 0
        for j in range(1, 7):
            for k in range(1, 16):
                res += dp[n][j][k]
                res %= mod
        return res

import functools

mod = 10 ** 9 + 7
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        def memo(f):
            d = defaultdict()
            
            def inner(*args):
                if d.get(args) is None:
                    d[args] = f(*args)
                return d[args]
            return inner
        
        @functools.lru_cache(maxsize=n*16)
        def inner(n, last, last_n):
            if n == 0:
                return 1
            
            
            r = list(range(1, 7))
            
            if last and last_n >= rollMax[last - 1]:
                del r[last - 1]
            
            res = [
                inner(n - 1, i, 1 if i != last else last_n + 1) for i in r
            ]
            
            return sum(res)
        
        
        return inner(n, None, None) % mod


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10 ** 9 + 7
        dp = [[0] * (n + 1) for _ in range(7)]
        for j in range(1, n + 1):
            tot = sum(dp[k][j - 1] for k in range(1, 7)) 
            for i in range(1, 7):
                if j == 1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = tot
                    if j > rollMax[i - 1] + 1:
                        dp[i][j] -= sum(dp[k][j - rollMax[i - 1] - 1] for k in range(1, 7) if k != i) - mod
                    elif j == rollMax[i - 1] + 1:
                        dp[i][j] -= 1
                    dp[i][j] %= mod
        # print(dp)
        return sum(dp[k][n] for k in range(1, 7)) % mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        
        
        def helper(n, last, count):
            key = (n, last, count)
            if key in d:
                return d[key]
            if n == 0:
                return 1
            
            ans = 0
            for i in range(6):
                if i == last and count == rollMax[i]:
                    continue
                if i == last:
                    ans += helper(n - 1, i, count + 1)
                else:
                    ans += helper(n - 1, i, 1)
                
            d[key] = ans
            return d[key]
        d = dict()
        return helper(n, -1, 0) % (10**9 + 7)

MOD = int(1e9 + 7)

class Solution:
    def get(self, n, d, l):
        if n == 1:
            return 5 if l == 0 else 6
        
        try:
            return self.cache[(n, d, l)]
        except KeyError:
            ret = 0
            for e in range(6):
                if e == d:
                    if l > 0:
                        ret += self.get(n - 1, d, l - 1)
                        ret %= MOD   
                else:
                    ret += self.get(n - 1, e, self.limits[e] - 1)
                    ret %= MOD
            self.cache[(n, d, l)] = ret
            return ret
                
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.limits = rollMax
        self.cache = {}
        
        for nn in range(2, n - 1 + 1):
            for d in range(6):
                for l in range(self.limits[d] - 1 + 1):
                    self.get(nn, d, l)
        ret = 0
        for d in range(6):
            ret += self.get(n - 1, d, self.limits[d] - 1)
            ret %= MOD
        return ret

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        memo ={}
        
        def dfs(nLeft, last, curLen):
            if (nLeft, last, curLen) in memo:
                return memo[(nLeft, last, curLen)]
            if nLeft == 0:
                return 1
            cnt = 0
            for i in range(6):
                if i==last and rollMax[i] == curLen:
                    continue
                cnt += dfs(nLeft-1, i, curLen+1 if i==last else 1 )
            
            memo[(nLeft, last, curLen)] = cnt
            return memo[(nLeft, last, curLen)]
                    
        return dfs(n, 0, 0)%(10**9+7)
    
    
#         self.res = 0
        
        
#         def dfs(nLeft, last, curLen):
#             if nLeft == 0:
#                 self.res += 1
#                 return
            
#             for i in range(6):
#                 if i==last and rollMax[i] == curLen:
#                     continue
#                 dfs(nLeft-1, i, curLen+1 if i==last else 1 )
#             return
            
#         dfs(n, 0, 0)
        
#         return self.res
    


from collections import defaultdict

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        MOD = 10**9 + 7
        
        dice = defaultdict(int)
        mem = {}
        
        def helper(i, predie, count):
            if i == n:
                return 1
            
            if (i,predie,count) in mem:
                return mem[(i,predie,count)]
            
            
            out = 0
            for die in range(6):
                if die == predie and count == rollMax[die]:
                    continue
                v, c = die, 1
                if die == predie:
                    c = count + 1
                out += helper(i+1, v, c) 
                    
            mem[(i,predie,count)] = out % MOD
                    
            return mem[(i,predie,count)]
        
        
        
        return helper(0, -1, -1)
            
            
            
            
            


from collections import defaultdict
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = pow(10, 9) + 7
        rollMax = [0] + rollMax
        for i in range (len(rollMax)):
            rollMax [i] = min(n, rollMax[i])
        
        cache = defaultdict(int)
        def dp (last, consec, pos):
            if pos == n:
                return 1
            if (last, consec, pos) in cache:
                return cache[(last, consec, pos)]
            ans = 0
            for i in range (1, 7):
                if last == i:
                    if consec < rollMax[i]:
                        ans += dp(i, consec + 1, pos + 1)
                else:
                    ans += dp(i, 1, pos + 1)
            cache[(last, consec, pos)] = ans 
            return ans
        
        return dp(0, 0, 0) % mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        return self.helper(n, rollMax, 0, 0, {}) % MOD
        
    def helper(self, n, rollMax, last, times, cache):
        if (n, last, times) in cache:
            return cache[(n, last, times)]
        
        if n == 0:
            return 1
        
        res = 0
        for i in range(6):
            if last != i + 1:
                res += self.helper(n - 1, rollMax, i + 1, 1, cache)
            elif rollMax[i] > times:
                res += self.helper(n - 1, rollMax, last, times + 1, cache)
                
        cache[(n, last, times)] = res
        return res

from functools import lru_cache
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = {}
        
        def roll(value, consecutiveRolls, left):
            if left == 0:
                return 1
            
            if (value,consecutiveRolls,left) in dp:
                return dp[value,consecutiveRolls,left]
            #print(value, consecutiveRolls, left)
            #if dp[value][consecutiveRolls][left] != -1:
            #    return dp[value][consecutiveRolls][left]
            
            rolls = 0
            for i in range(6):
                if i != value:
                    rolls += roll(i, 1, left-1)
                else:
                    if consecutiveRolls < rollMax[i]:
                        rolls += roll(i, consecutiveRolls+1, left-1)
            
            dp[value,consecutiveRolls,left] = rolls
            
            return rolls
        
        return roll(0,0,n) % (10**9 + 7)
                    


import functools

mod = 10 ** 9 + 7
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        def memo(f):
            d = defaultdict()
            
            def inner(*args):
                if d.get(args) is None:
                    d[args] = f(*args)
                return d[args]
            return inner
        
        @functools.lru_cache(maxsize=n*n)
        def inner(n, last, last_n):
            if n == 0:
                return 1
            
            
            r = list(range(1, 7))
            
            if last and last_n >= rollMax[last - 1]:
                del r[last - 1]
            
            res = [
                inner(n - 1, i, 1 if i != last else last_n + 1) for i in r
            ]
            
            return sum(res)
        
        
        return inner(n, None, None) % mod


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mode = (10**9 + 7)
        memo = {}
        def dfs(prev , s , n):
            if n == 0:
                return 1
            
            if(prev,s,n) in memo:
                return memo[(prev,s,n)]
            
            else:
                res = 0
                for i in range(6):
                    if i == prev:
                        if s +  1 > rollMax[i]:
                            continue
                        else:
                            res += dfs(i, s + 1 , n - 1)
                    
                    else:
                        res += dfs(i, 1 , n -1)
                memo[(prev,s,n)] = res 
                
            return res
        
        return dfs(-1 , 0, n)%mode


# from function
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        res=0
        mod=10**9+7
        @lru_cache(maxsize=None)
        def dfs(n,val,count):
            if not n:
                return 1
            t=0
            for i in range(6):
                if i!=val:
                    t+=dfs(n-1,i,1)
                elif i==val and  count<rollMax[i]:
                    t+=dfs(n-1,val,count+1)
            # t%=mod
            return t
        return sum(dfs(n-1,i,1) for i in range(6))%mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = {}
        
        def roll(value, consecutiveRolls, left):
            if left == 0:
                return 1
            
            if (value,consecutiveRolls,left) in dp:
                return dp[value,consecutiveRolls,left]
            #print(value, consecutiveRolls, left)
            #if dp[value][consecutiveRolls][left] != -1:
            #    return dp[value][consecutiveRolls][left]
            
            rolls = 0
            for i in range(6):
                if i != value:
                    rolls += roll(i, 1, left-1)
                else:
                    if consecutiveRolls < rollMax[i]:
                        rolls += roll(i, consecutiveRolls+1, left-1)
            
            dp[value,consecutiveRolls,left] = rolls
            
            return rolls
        
        return roll(0,0,n) % (10**9 + 7)
                    


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        modVal = 10**9 + 7
        memo = {}
        def recurse(numLeft, prevNum, prevNumCount):
            if numLeft == 0:
                return 1
            
            if (numLeft, prevNum, prevNumCount) in memo:
                return memo[(numLeft, prevNum, prevNumCount)]
            
            numWays = 0
            for i in range(len(rollMax)):
                if i == prevNum:
                    if prevNumCount < rollMax[i]:
                        numWays += recurse(numLeft - 1, i, prevNumCount + 1)
                else:
                    numWays += recurse(numLeft - 1, i, 1)
            
            memo[(numLeft, prevNum, prevNumCount)] = numWays
            
            return numWays
        
        return recurse(n, -1, -1) % modVal

class Solution:
    # 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.
    # count[0][f] = 0 and total[0] = 1.
    # for each throw, check the number of ways to after ith throw and the end face is f
    # def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        
        
        
    # DFS with memoization.
    # State to remember (#throws_left, #repeat, last_face)
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        cache = collections.defaultdict()
        
        def dfs(n, repeat, face):
            if n == 0:
                return 1
            elif (n, repeat, face) in cache:
                return cache[(n, repeat, face)]
            else:
                count = 0
                for f in range(6):
                    if f != face:
                        count += dfs(n - 1, 1, f)
                    else:
                        if repeat + 1 <= rollMax[f]:
                            count += dfs(n - 1, repeat + 1, f)
                cache[(n, repeat, face)] = count
                return count
            
        return sum(dfs(n - 1, 1, f) for f in range(6)) % (10**9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        def rec(die, cons, empty):
            if empty == 0:
                return 1

            ans = 0
            if (die, cons, empty) in dp:
                return dp[(die, cons, empty)]
            for r in range(6):
                if r != die:
                    ans += rec(r, 1, empty - 1)
                elif cons < rollMax[die]:
                    ans += rec(die, cons + 1, empty - 1)
            dp[(die, cons, empty)] = ans
            return ans
        dp = {}
        return rec(0, 0, n) % (10 ** 9 + 7)


# class Solution:
#     def dieSimulator(self, n: int, rollMax: List[int]) -> int:
#         def f(n, num, co):
            
#             if n == 0:
#                 return 1
            
#             if (n, num, co) in dp:
#                 return dp[n, num, co]
            
#             ans = 0
#             for i in range(1, 7):
#                 if i == num and co + 1 <= rollMax[i - 1]:
#                     ans += f(n - 1, i, co + 1)
#                 else:
#                     ans += f(n - 1, i, 1)
#             dp[n, num, co] = ans
#             return ans

#         dp = {}
#         return f(n, 0, 0) % (10 ** 9 + 7)





class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mode = (10**9 + 7)
        memo = {}
        def dfs(prev , s , n):
            if n == 0:
                return 1
            
            if(prev,s,n) in memo:
                return memo[(prev,s,n)]
            
            else:
                res = 0
                for i in range(6):
                    if i == prev:
                        if s +  1 > rollMax[i]:
                            continue
                        else:
                            res += dfs(i, s + 1 , n - 1)
                    
                    else:
                        res += dfs(i, 1 , n -1)
                memo[(prev,s,n)] = res 
                
            return res
        
        return dfs(0 , 0, n)% mode


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        rollMax.insert(0, None)
        memo = {}
        def recurse(curr_n, curr_num, seq_length):
            if (curr_n, curr_num, seq_length) in memo:
                return memo[(curr_n, curr_num, seq_length)]
            
            if curr_n == n:
                return 1
            comb = 0
            for i in range(1, len(rollMax)):
                if i == curr_num and rollMax[i] - seq_length > 0:
                    comb += recurse(curr_n + 1, curr_num, seq_length + 1)
                elif i != curr_num:
                    comb += recurse(curr_n + 1, i, 1)
            memo[(curr_n, curr_num, seq_length)] = comb
            return comb
        combs = 0
        for i in range(1, 7):
            combs += recurse(1, i, 1)
        return combs % 1000000007


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        cache = {}
        
        @lru_cache(maxsize=None)
        def dfs(n, i, k):
            if not n: return 1
            ans = 0
            for j in range(6):
                if i != j: ans += dfs(n-1, j, 1)
                elif k+1 <= rollMax[j]: ans += dfs(n-1, j, k+1)
            return ans    
        return sum(dfs(n-1, i, 1) for i in range(6)) % 1000000007


from functools import lru_cache

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.rollMax = rollMax
        return self.solve(n, -1, 0) % (1000000007)
        
    @lru_cache(maxsize=1024, typed=False)
    def solve(self, n, last_index=-1, last_times=0):
        if n == 0:
            return 1
        else:
            res = 0
            for i in range(6):
                if i == last_index and self.rollMax[i] > last_times:
                    res += self.solve(n - 1, i, last_times + 1)
                elif i != last_index:
                    res += self.solve(n - 1, i, 1)

            return res


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        def g(n,k):
            if n < 1: return 0
            if n == 1: return 1
            if (n,k) in g_cache:
                return g_cache[(n,k)]
            ans = f(n-1) - f(n-rollMax[k-1]-1) + g(n-rollMax[k-1]-1,k)
            g_cache[(n,k)] = ans
            return ans

        def f(n):
            if n < 0 : return 0
            if n == 0 : return 1
            if n in f_cache:
                return f_cache[n]
            
            ans = sum([g(n,k) for k in range(1,7)])
            f_cache[n] = ans
            return ans
            
        g_cache = {}
        f_cache = {}

        return f(n) % (10 ** 9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        for i in range(len(rollMax)):
            rollMax[i] = min(rollMax[i], n)
        dp = []
        max_roll = max(rollMax) + 1
        for k in range(n + 1):
            dp.append([])
            for i in range(6):
                dp[-1].append([])
                for j in range(max_roll):
                    if k == 1 and j > 0:
                        dp[-1][-1].append(1)
                    else:
                        dp[-1][-1].append(0)

        MOD = (10 ** 9) + 7
        for k in range(1, n + 1):
            for prev_roll in range(6):
                for cur_roll in range(6):
                    for j in range(1, max_roll):
                        if prev_roll == cur_roll:
                            dp[k][prev_roll][j] += dp[k - 1][prev_roll][j - 1]
                        else:
                            dp[k][prev_roll][j] += dp[k - 1][cur_roll][rollMax[cur_roll]]
        ans = 0
        for i in range(6):
            ans += dp[n][i][rollMax[i]]
        return ans % MOD


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = []
        max_roll = max(rollMax) + 1
        for k in range(n + 1):
            dp.append([])
            for i in range(6):
                dp[-1].append([])
                for j in range(max_roll):
                    if k == 1 and j > 0:
                        dp[-1][-1].append(1)
                    else:
                        dp[-1][-1].append(0)

        MOD = (10 ** 9) + 7
        for k in range(1, n + 1):
            for prev_roll in range(6):
                for cur_roll in range(6):
                    for j in range(1, max_roll):
                        if prev_roll == cur_roll:
                            dp[k][prev_roll][j] += dp[k - 1][prev_roll][j - 1]
                        else:
                            dp[k][prev_roll][j] += dp[k - 1][cur_roll][rollMax[cur_roll]]
        ans = 0
        for i in range(6):
            ans += dp[n][i][rollMax[i]]
        return ans % MOD


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        memo = {}
        def dfs(last, s,  k):
            if k == n:
                return 1
            if (last, s, k)  in memo:
                return memo[last, s, k]
            
            else:
                
                res = 0
                for i in range(6):
                    if i == last:
                        if s + 1 > rollMax[i]:
                            continue
                        else:
                            res += dfs(i, s+1, k+1)
                    else:
                        res += dfs(i, 1, k+1)
                memo[last, s, k] = res
            return res
        
        
        mode = 10**9 + 7
        return dfs(None, 0, 0)%mode


from functools import lru_cache
class Solution:
    def __init__(self):
        self.result = 0
    
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @lru_cache(maxsize=None)
        def helper(last_val: int, streak_count: int, size: int):
            if size == n:
                return 1
            result = 0
            for i in range(len(rollMax)):
                if last_val != i:
                    result += helper(i, 1, size + 1)
                elif streak_count + 1 <= rollMax[i]:
                    result += helper(i, streak_count + 1, size + 1)
            return result
        return helper(-1, 1, 0) % (10**9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        memo = {}
        def dfs(last, s,  k):
            if k == n:
                return 1
            if (last, s, k) not in memo:
                res = 0
                for i in range(6):
                    if i == last:
                        if s + 1 > rollMax[i]:
                            continue
                        else:
                            res += dfs(i, s+1, k+1)
                    else:
                        res += dfs(i, 1, k+1)
                memo[last, s, k] = res
            return memo[last, s, k]
        
        
        return dfs(None, 0, 0)%(10**9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.mod = 10**9+7
        self.memo = {}

        def helper(rolls, last, freq):
            if rolls==0:
                return 1
            if (rolls, last, freq) in self.memo:
                return self.memo[(rolls, last, freq)]
            count = 0
            for j in range(len(rollMax)):
                if j==last:
                    if freq<rollMax[j]:
                        count += (helper(rolls-1, j, freq+1))%self.mod
                else:
                    count += (helper(rolls-1, j, 1))%self.mod
            self.memo[(rolls, last, freq)] = count%self.mod
            return count%self.mod
        
        count = 0
        for i in range(6):
            count += helper(n-1, i, 1)
        return count%self.mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[[0]*16 for _ in range(6)]for _ in range(n)]
        
        for i in range(6):
            dp[0][i][1] = 1
            
        MOD = 10**9+7
        
        for i in range(1, n):
            for j in range(6):
                for k in range(6):
                    if j!=k:
                        for l in range(16):
                            dp[i][j][1] += dp[i-1][k][l]
                            dp[i][j][1] %= MOD
                    else:
                        for l in range(rollMax[j]):
                            dp[i][j][l+1] += dp[i-1][k][l]
                            dp[i][j][l+1] %= MOD
        
        ans = 0
        
        for i in range(6):
            for j in range(16):
                ans += dp[n-1][i][j]
                ans %= MOD
        
        return ans

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @lru_cache(maxsize=None)
        
        # @func DFS: depth-first search on the chance of rolling a given combination
        # @param n: the number of chances you have left to roll
        # @param i: the number you roll
        # @param k: counter for the number of times this number was repeated
        def DFS(n, i, k):
            # If there is no more chances left (this is a combination)..
            if not n:
                # Count the combintation as a single one
                return 1
            
            # Create a counter to determine the number of possible combintations with this configuration
            numSequences = 0
            
            # For each roll of the die
            for j in range(6):
                # If this element is not the one currently rolled..
                if not i == j:
                    # Add the combination sequences, of this given i, then j sequence
                    numSequences += DFS(n - 1, j, 1)
                
                # If adding another roll of this element is possible given the constraints..
                elif k + 1 <= rollMax[j]:
                    # Add the combintation sequence, of this given i, then i (technically j)
                    numSequences += DFS(n - 1, j, k + 1)
            
            return numSequences
        
        return sum(DFS(n - 1, i, 1) for i in range(6)) % 1000000007


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        m = max(rollMax)
        dp = [[1]+[0]*(m-1) for _ in range(len(rollMax))]
        MOD = 1e9+7
        for i in range(1, n):
            tempSumPrev = [0]*len(rollMax)
            tempDp = [[0]*m for _ in range(len(rollMax))]
            totalSumPrev = 0
            for p in dp:
                for q in p:
                    totalSumPrev = (totalSumPrev+q)%MOD
            for j in range(len(rollMax)):
                tempDp[j][0] = totalSumPrev-sum(dp[j])
                for k in range(1, rollMax[j]):
                    tempDp[j][k] = dp[j][k-1]
            dp = tempDp
        return int(sum(q for p in dp for q in p)%MOD)

class Solution:
    def __init__(self):
        self.dp = [] 
        
    def utility(self, n, rollMax, lastVal, count):
        if n == 0:
            return 1
        
        if self.dp[n][lastVal][count] is not None:
            return self.dp[n][lastVal][count]
        
        ans=0
        for i in range(1, 7):
            if lastVal == i:
                if rollMax[lastVal-1] > count:
                    ans += self.utility(n-1, rollMax, lastVal, count+1)
                else:
                    continue
            else:
                ans += self.utility(n-1, rollMax, i, 1) 

            
        self.dp[n][lastVal][count] = ans % 1000000007

        return self.dp[n][lastVal][count]
        
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.dp = [[[None for i in range(16)] for j in range(7)] for k in range(5001)]
        return self.utility(n, rollMax, -1, 0)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        cache = {}
        
        def dfs(c,l,d):
            nonlocal n
            nonlocal rollMax
            
            key = tuple([c,l,d])
            
            if key in cache:
                return cache[key]
            
            if rollMax[l] < d:
                return 0
            
            if c == n:
                return 1
            
            sm = 0
            
            for i in range(0,6):
                sm += dfs(c+1,i,1+d*(i==l))
                    
            cache[key] = sm
            
            return sm
        
        return dfs(0,-1,0)%(10**9 +7)

from functools import lru_cache
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @lru_cache(None)
        def helper(rolls, side, count):
            if not rolls:
                return 1
            res = 0
            for i in range(6):
                if i != side:
                    res += helper(rolls - 1, i, 1)
                elif count + 1 <= rollMax[side]:
                    res += helper(rolls - 1, side, count + 1)
            return res
        return sum(helper(n-1, i, 1) for i in range(6)) % (10 ** 9 + 7)


from functools import lru_cache
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        @lru_cache(None)
        def roll(val,cons,roll_left):
            if roll_left == 0:
                return 1
            total_ways = 0
            for i in range(6):
                if i == val:
                    continue
                total_ways += roll(i,1,roll_left-1)
            if cons < rollMax[val]:
                total_ways += roll(val,cons+1,roll_left-1)
            return total_ways
        
        return roll(0,0,n) % (10**9 + 7)


sys.setrecursionlimit(100000)
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        @lru_cache(None)
        def f(n, last, consec):
            if n == 0: return 1
            if consec < rollMax[last]:
                A = f(n-1, last, consec+1)
            else:
                A = 0
            return (A + sum(f(n-1, i, 1) for i in range(6) if i != last)) % (10**9+7)
        return f(n, 0, 0)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[[0 for k in range(16)]for j in range(6)]for i in range(5000)]
        
        M = 10 ** 9 + 7
        
        def dfs(dies, last, cur_len):
            if not dies:
                # print(curr_roll)
                return 1
            
            if last >= 0 and dp[dies][last][cur_len] > 0:
                return dp[dies][last][cur_len]
            
            ret = 0
            
            for i in range(6):
                if cur_len == rollMax[i] and i == last:
                    continue
                
                nxt = 0
                
                if last == i:
                    nxt = cur_len + 1
                else:
                    nxt = 1
                    
                ret += dfs(dies - 1, i, nxt)
                ret %= M
                
            if last >= 0:
                dp[dies][last][cur_len] = ret
            
            return ret
        
        return dfs(n, -1, 0)

class Solution:
    def dieSimulator(self, N: int, rollMax: List[int]) -> int:
        
        def dp(curr_cnt, curr, n):
            # print (curr_cnt, curr,n, rollMax[curr-1], curr_cnt)
            if curr>0 and rollMax[curr-1]<curr_cnt:
                return 0
            elif n==0:
                return 1
            elif (curr_cnt, curr, n) in memo:
                return memo[(curr_cnt, curr, n)]
            else:
                res = 0
                for i in range(1, 7):
                    if i==curr:
                        res += dp(curr_cnt+1, i, n-1)
                    else:
                        res += dp(1, i, n-1)
                memo[(curr_cnt, curr, n)] = res
                return res
            
        memo = dict()
        res = dp(0, 0, N)
        return res%(10**9+7)


from functools import lru_cache
class Solution:
    def dieSimulator(self, n, roll_max):

        dicti = {}
        
        def dp(roll, last, count):
            if not roll:
                return 1
            elif (roll, last, count) in dicti:
                return dicti[(roll, last, count)]
            
            ans = 0
            for i in range(6):
                if i != last:
                    ans += dp(roll-1, i, 1)
                elif count < roll_max[i]:
                    ans += dp(roll-1, last, count+1)
            dicti[roll, last, count] = ans % (10**9 + 7)
            return dicti[roll, last, count]
        return dp(n, -1, 0)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        cache = {}
        
        def dfs(c,l,d):
            nonlocal n
            nonlocal rollMax
            
            key = tuple([c,l,d])
            
            if key in cache:
                return cache[key]
            
            if c == n:
                return 1
            
            sm = 0
            
            for i in range(0,6):
                if i != l or d != rollMax[i]:
                    sm += dfs(c+1,i,1+d*(i==l))
                    
            cache[key] = sm
            
            return sm
        
        return dfs(0,-1,0)%(10**9 +7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        maxv = max(rollMax)
        dp = [[[0] * (maxv + 1) for _ in range(6)] for _ in range(n + 1)]
        
        for j in range(6):
            dp[1][j][1] = 1
        prev_total = 6
            
        for n in range(2, n + 1):
            new_total = 0
            for roll_num in range(6):
                one = prev_total - sum(dp[n - 1][roll_num])
                dp[n][roll_num][1] = one % 1000000007
                for k in range(2, rollMax[roll_num] + 1):
                    dp[n][roll_num][k] = dp[n - 1][roll_num][k - 1]
                new_total += sum(dp[n][roll_num])
            prev_total = new_total
        return sum(sum(dp[-1][number]) for number in range(6)) % 1000000007

from functools import lru_cache
class Solution:
    def dieSimulator(self, n, roll_max):

        dicti = {}
        
        def dp(roll, last, count):
            if not roll:
                return 1
            elif (roll, last, count) in dicti:
                return dicti[roll, last, count]
            
            ans = 0
            for i in range(6):
                if i != last:
                    ans += dp(roll-1, i, 1)
                elif count < roll_max[i]:
                    ans += dp(roll-1, last, count+1)
            dicti[roll, last, count] = ans % (10**9 + 7)
            return dicti[roll, last, count]
        return dp(n, -1, 0)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.memo = defaultdict(int) # (n, prev) -> bool
        self.ans = 0
        def helper(n, prev, m):
            if n == 0:
                return 1
            if self.memo[(n,prev,m)] > 0: 
                return self.memo[(n,prev,m)]
            ans = 0
            for i in range(6):
                if prev == i:
                    if m >= rollMax[i]:
                        continue
                
                    ans += helper(n-1, i, m+1)
                else:
                    ans += helper(n-1, i, 1)
            self.memo[(n,prev,m)] = ans
            return ans
        return helper(n, -1, 0) % (10**9 + 7)


from functools import lru_cache

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.rollMax = rollMax
        return self.solve(n, -1, 0) % (1000000007)
        
    @lru_cache(maxsize=4096 * 2, typed=False)
    def solve(self, n, last_index=-1, last_times=0):
        if n == 0:
            return 1
        else:
            res = 0
            for i in range(6):
                if i == last_index and self.rollMax[i] > last_times:
                    res += self.solve(n - 1, i, last_times + 1)
                elif i != last_index:
                    res += self.solve(n - 1, i, 1)

            return res


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        return self.dieSimulator_recursive(n, rollMax)
    
    def dieSimulator_recursive(self, n: int, rollMax: List[int]) -> int:
        if n == 0:
            return 0
        
        memo = {}
        def f(n, d, r):
            if n == 1:
                return 1
            
            if (n, d, r) in memo:
                return memo[(n, d, r)]
            
            total = 0
            for nd in range(6):
                if nd != d:
                    total += f(n - 1, nd, 1)
            if r < rollMax[d]:
                total += f(n - 1, d, r + 1)
            
            memo[(n, d, r)] = total
            return total % (10**9 + 7)
        
        total = 0
        for d in range(6):
            total += f(n, d, 1)
        return total % (10**9 + 7)

        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        if n == 0:
            return 0
        
        memo = {}
        def f(d, r, n):
            if n == 1:
                return 1
            
            if (d, r, n) in memo:
                return memo[(d, r, n)]
            
            total = 0
            for nd in range(6):
                if nd != d:
                    total += f(nd, 1, n - 1)
            if r < rollMax[d]:
                total += f(d, r + 1, n - 1)
            
            memo[(d, r, n)] = total
            return total % (10**9 + 7)
        
        total = 0
        for d in range(6):
            total += f(d, 1, n)
        return total % (10**9 + 7)
                    
                    
            
        f = [None] * n
        for i in range(0, n):
            f[i] = [None] * 6
            for d in range(6):
                if i == 0:
                    f[i][d] = [1] * rollMax[d]
                    continue
                    
                f[i][d] = [0] * rollMax[d]
                for r in range(rollMax[d]):
                    f[i][d][r] += f[i-1][d][r-1] if r-1 >= 0 else 0
                
                for r in range(rollMax[d]):
                    for nd in range(6):
                        if nd != d:
                            f[i][d][r] += f[i-1][nd][0]
                            
        total = 0
        for d in range(len(f[n-1])):
            total += f[n-1][d][rollMax[d]-1]
        return total
                
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # imagine blank spaces equal to 
        # the number of rolls
        
        # _ _ _ _ 
        
        # every time we roll, it could be any of 1-6 numbers
        
        # so imagine the first number is 1
        # what are possibilities for the rest
        # the rest can again be
        
        # what do we want function to return.
        # instead of returning, can just increment count when reaching the end
        
        cache = {}
        
        def sim(n, count, curr_element):    
            if curr_element:
                if count > rollMax[curr_element-1]:
                    return float('inf')
                
            if (n,count,curr_element) in cache:
                return cache[(n,count,curr_element)]
            
            if n==0:
                return 1

            # basically how many ways can I reach end from current point
            all_ans = 0
            for i in range(1,7):
                if curr_element == i:
                    ans = sim(n-1, count+1, i)
                else:
                    ans = sim(n-1, 1, i)
                    
                if ans!=float('inf'):
                    all_ans += ans 
                    
            cache[(n,count, curr_element)] = all_ans
            return all_ans
                
        
        return sim(n, 0, 0) % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        memo = {}
        def f(d, r, n):
            if n == 1:
                return 1
            
            if (d, r, n) in memo:
                return memo[(d, r, n)]
            
            total = 0
            for nd in range(6):
                if nd != d:
                    total += f(nd, 1, n - 1)
            if r < rollMax[d]:
                total += f(d, r + 1, n - 1)
            
            memo[(d, r, n)] = total
            return total % (10**9 + 7)
        
        total = 0
        for d in range(6):
            total += f(d, 1, n)
        return total % (10**9 + 7)
                    
                    
            
        f = [None] * n
        for i in range(0, n):
            f[i] = [None] * 6
            for d in range(6):
                if i == 0:
                    f[i][d] = [1] * rollMax[d]
                    continue
                    
                f[i][d] = [0] * rollMax[d]
                for r in range(rollMax[d]):
                    f[i][d][r] += f[i-1][d][r-1] if r-1 >= 0 else 0
                
                for r in range(rollMax[d]):
                    for nd in range(6):
                        if nd != d:
                            f[i][d][r] += f[i-1][nd][0]
                            
        total = 0
        for d in range(len(f[n-1])):
            total += f[n-1][d][rollMax[d]-1]
        return total
                
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        memo = {}
        # @lru_cache(None)
        def helper(n, consec):
            # consec: [0,2] already roll 1 twice
            if rollMax[consec[0]] < consec[1]:
                return 0
            elif n == 0:
                return 1
            elif (n, consec) in memo:
                return memo[(n, consec)]

            res = []
            for i in range(1, 7):
                if i - 1 ==  consec[0]:
                    res.append(helper(n-1, (consec[0], consec[1] + 1)))
                else:
                    res.append(helper(n-1, (i-1, 1)))
            # print(n , res, sum(res), sum(res) % (10**9+7))
            memo[(n,consec)] = sum(res) % (10**9+7)
            return memo[(n,consec)]
        
        return helper(n, (0,0))


from functools import lru_cache
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
       
        
        @lru_cache(None)
        def r(v,p,c):
            if c==n:
                return 1
            else:
                t = 0
                for i in range(0,6):
                    if i==p:
                        if v<rollMax[i]:
                            t+=r(v+1,i,c+1)
                    else:
                        t+=r(1,i,c+1)
                        
                return t
            
        return r(0,0,0)%(10**9 + 7)

from random import randint

mod = 10 ** 9 + 7
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        def memo(f):
            d = defaultdict()
            
            def inner(*args):
                if d.get(args) is None:
                    d[args] = f(*args)
                return d[args]
            return inner
        
        @memo
        def inner(n, last, last_n):
            if n == 0:
                return 1
            
            
            r = list(range(1, 7))
            
            if last and last_n >= rollMax[last - 1]:
                del r[last - 1]
            
            res = [
                inner(n - 1, i, 1 if i != last else last_n + 1) for i in r
            ]
            
            return sum(res)
        
        
        return inner(n, None, None) % mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # imagine blank spaces equal to 
        # the number of rolls
        
        # _ _ _ _ 
        
        # every time we roll, it could be any of 1-6 numbers
        
        # so imagine the first number is 1
        # what are possibilities for the rest
        # the rest can again be
        
        # what do we want function to return.
        # instead of returning, can just increment count when reaching the end
        
        self.count = 0
        cache = {}
        
        def sim(n, count, curr_element):    
            if curr_element:
                if count > rollMax[curr_element-1]:
                    return float('inf')
                
            if (n,count,curr_element) in cache:
                return cache[(n,count,curr_element)]
            
            if n==0:
                self.count  +=1
                return 1

            # basically how many ways can I reach end from current point
            all_ans = 0
            for i in range(1,7):
                if curr_element == i:
                    ans = sim(n-1, count+1, i)
                else:
                    ans = sim(n-1, 1, i)
                    
                if ans!=float('inf'):
                    all_ans += ans 
                    
            cache[(n,count, curr_element)] = all_ans
            #print (n,count,curr_element)
            return all_ans
                
        #print (sim(n, 0, 0))
        
        return sim(n, 0, 0) % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.memo = [[[0 for k in range(16)] for j in range(6)] for i in range(5001)]
        def helper(n, prev, m):
            if n == 0:
                return 1
            if self.memo[n][prev][m] > 0: 
                return self.memo[n][prev][m]
            ans = 0
            for i in range(6):
                if prev == i:
                    if m >= rollMax[i]:
                        continue
                
                    ans += helper(n-1, i, m+1)
                else:
                    ans += helper(n-1, i, 1)
            self.memo[n][prev][m] = ans
            return ans
        return helper(n, -1, 0) % (10**9 + 7)


M = int(1e9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        self.roll_max = rollMax
        self.cache = {}
        return self._dfs(n, -1, 0)
    
    def _dfs(self, rolls_left: int, prev_roll: int, curr_len: int) -> None:
        if rolls_left == 0:
            return 1
        
        if (rolls_left, prev_roll, curr_len) in self.cache:
            return self.cache[(rolls_left, prev_roll, curr_len)]
        
        result = 0
        for i in range(6):
            if i == prev_roll and curr_len >= self.roll_max[i]:
                continue
                
            result += self._dfs(rolls_left - 1, i, curr_len + 1 if i == prev_roll else 1)

        result %= M 
        self.cache[(rolls_left, prev_roll, curr_len)] = result
        return result
        
        


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        if n == 1:
            return 6
        mem = {}
        def get_dp(n, d, c):
            if n==1:
                return 6 if c < rollMax[d-1] else 5
            elif (n, d, c) not in mem:
                mem[n, d, c] = 0
                for d_ in range(1, 7):
                    if d_ != d:
                        mem[n, d, c] += get_dp(n-1, d_, 1)
                    elif c < rollMax[d-1]:
                        mem[n, d, c] += get_dp(n-1, d, c+1)
            return mem[n, d, c]
        result = sum(get_dp(n-1, d, 1) for d in range(1, 7))
        result = result % int(10**9+7)
        return result

from functools import lru_cache
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        @lru_cache(maxsize=None)
        def dfs(left, numConsecutive, last):
            total = 0
            if left == 0:
                if numConsecutive <= rollMax[last]:
                    return 1
                else:
                    return 0
            for i in range(6):
                if i == last:
                    if numConsecutive + 1 <= rollMax[last]:
                        total += dfs(left - 1, numConsecutive + 1, i)
                else:
                    total += dfs(left - 1, 1, i)
            return total 
        
        return dfs(n, 0, -1) % (10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        m=max(rollMax)
        dp=[[0 for i in range(m)] for j in range(6)]
        for i in range(6):
            dp[i][0]=1
        total=6
        for i in range(n-1):
            new_dp=[[0 for i in range(m)] for j in range(6)]
            new_total=0
            for j in range(6):
                new_dp[j][0]=total-sum(dp[j])
                new_dp[j][0]%=(10**9+7)
                new_total+=new_dp[j][0]
                new_total%=(10**9+7)
                for k in range(1,rollMax[j]):
                    new_dp[j][k]=dp[j][k-1]
                    new_total+=new_dp[j][k]
            dp=new_dp
            total=new_total%(10**9+7)
        return total%(10**9+7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[1 for _ in range(6)] for _ in range(n)]
    
        for i in range(1, n):
            for j in range(6):
                inc = sum(dp[i-1])
                prev = i - rollMax[j] - 1
                if prev == -1:
                    inc -= 1
                elif prev >= 0:
                    for k in range(6):
                        if k == j:
                            continue
                        inc -= dp[prev][k]
                dp[i][j] = inc
        # print(dp)
        return sum(dp[-1]) % (10 ** 9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        N = n
        faces = len(rollMax)
        MOD = 7 + 10**9
        
        dp = [[0 for _ in range(faces+1)] for _ in range(N+1)]
        
        dp[0][faces] = 1
        
        for i in range(faces):
            dp[1][i] = 1
        
        dp[1][faces] = faces
        
        for i in range(2, N+1):
            for j in range(faces):
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    
                    dp[i][j] += dp[i-k][faces] - dp[i-k][j]
            
            dp[i][faces] = sum(dp[i]) % MOD
        
        return dp[N][faces] % MOD

MOD = int(1e9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp: List[List[int]] = [[0] * 6 for _ in range(n)]
        sums: List[int] = [0] * n
            
        # Init
        for j in range(6):
            dp[0][j] = 1
            
        sums[0] = sum(dp[0])
        
        # DP
        for i in range(1, n):
            for j in range(6):
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        dp[i][j] += 1
                        break

                    dp[i][j] += sums[i - k] - dp[i - k][j]
                    
            sums[i] = sum(dp[i]) % MOD
            
        return sums[-1]
   
# roll_max_2 = 3
# _, _, _, 2 = (_, _, !2, 2) + (_, !2, 2, 2) + (!2, 2, 2, 2)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # O(n + sum(rollMax))
        if n == 1: return 6
        states = []
        for i in rollMax:
            states.append([0]*i)
            states[-1][0] = 1
        
        sums = [0] * 6
        for i in range(1, n):
            for i in range(6):
                sums[i] = sum(states[i])
            
            for i in range(6):
                for j in reversed(list(range(len(states[i])))):
                    if j == 0:
                        states[i][0] = sum([sums[index] for index in range(6) if index != i]) % (10**9 + 7)
                    
                    else:
                        states[i][j] = states[i][j-1]
        
        return sum([sum(x) for x in states]) % (10**9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        M = 10**9+7
        memo = [[0]*sum(rollMax) for _ in range(n)]
        start = {0:0}
        for i in range(1, len(rollMax)):
            start[i] = start[i-1] + rollMax[i-1]
            
        
        
        for i in range(len(rollMax)):
            s = start[i]
            memo[0][s] = 1
        
        for i in range(1, n):
            for j in range(len(rollMax)):
                s = start[j]
                e = start[j] + rollMax[j]-1
                memo[i][s] = (sum(memo[i-1][:s])+sum(memo[i-1][e+1:])) % M
                for k in range(1,rollMax[j]):
                    memo[i][s+k] = memo[i-1][s+k-1]
        
        return sum(memo[-1]) % M


from typing import List

import numpy


class Solution:
  def dieSimulator(self, n: int, rollMax: List[int]) -> int:
    result = 0
    dims = (n + 1, 7)
    dp = numpy.zeros(dims, dtype=int)
    sums = [0] * (n + 1)
    kMod = 10 ** 9 + 7
    for j in range(0, 6):
      dp[1][j] = 1
      sums[1] += dp[1][j]


    for i in range(2, n+1):
      for j in range(6):
        k = i - rollMax[j]
        if k <= 1:
          invalid = max(k, 0)
        else:
          invalid = sums[k - 1] - dp[k-1][j]

        dp[i][j] = ((sums[i - 1] - invalid) % kMod + kMod) % kMod
        sums[i] = (sums[i] + dp[i][j]) % kMod
        pass
      pass

    return sums[-1]


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        m = max(rollMax)
        dp = [[[1]*m for _ in range(len(rollMax))] for _ in range(n)]
        dp[0] = [[1]+[0]*(m-1) for _ in range(len(rollMax))]
        MOD = 1e9+7
        sumPrev = [1]*len(rollMax)
        for i in range(1, n):
            tempSumPrev = [0]*len(rollMax)
            totalSumPrev = 0
            for p in sumPrev:
                totalSumPrev = (totalSumPrev+p)%MOD
            for j in range(len(rollMax)):
                dp[i][j][0] = totalSumPrev-sumPrev[j]
                s=dp[i][j][0]%MOD
                for k in range(1, rollMax[j]):
                    dp[i][j][k] = dp[i-1][j][k-1]
                    s = (s+dp[i][j][k])%MOD
                tempSumPrev[j] = s
            sumPrev = tempSumPrev
        return int(sum(sumPrev)%MOD)

class Solution:
    def dieSimulator(self,n, rollMax):
        if n==1:
            return 6
        mod = int(1e9+7)
        #init
        dp = [[0]*6 for i in range(n)]
        for j in range(6):
            dp[0][j] = 1
        sums = [0]*n
        sums[0] = 6
        #main process
        for i in range(1,n):
            #base case
            #sums[i-1]
            for j in range(6):
                invalid = 0
                k = i-rollMax[j]
                if k==0:
                    invalid = 1
                elif k>0:
                    invalid = sums[k-1] - dp[k-1][j]
                dp[i][j] = ((sums[i-1]-invalid)%mod+mod) % mod
                sums[i] = (sums[i] + dp[i][j]) % mod
        return sums[-1]

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0 for i in range(6)] for j in range(n)]
        for i in range(6):
            dp[0][i] = 1
        for i in range(1,n):
            total = sum(dp[i-1])
            for j in range(6):
                dp[i][j] += total
                if i-rollMax[j] == 0:
                    dp[i][j] -= 1
                if i-rollMax[j] > 0:
                    dp[i][j] -= sum(dp[i-rollMax[j]-1]) - dp[i-rollMax[j]-1][j]
        return sum(dp[n-1])%(10**9+7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        arr = []
        while n > 0:
            if not arr:
                arr.append([1 for _ in range(6)])
            else:
                cur_turn = [0 for _ in range(6)]
                for i in range(6):
                    if rollMax[i] > len(arr):
                        cur_turn[i] = sum(arr[-1])
                    else:
                        for k in range(1, 1+rollMax[i]):
                            cur_turn[i] += sum(arr[-k]) - arr[-k][i]
                cur_turn = [c % (10**9 + 7) for c in cur_turn]
                arr.append(cur_turn)
            n -= 1
        
        return sum(arr[-1]) % (10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        dp = [[0] * (faces + 1) for _ in range(n + 1)]
        mod = 10 ** 9 + 7
        dp[0][faces] = 1
        
        for i in range(faces):
            dp[1][i] = 1
        dp[1][faces] = faces
        
        
        for i in range(2, n+1):
            for j in range(faces):
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    dp[i][j] += (dp[i-k][faces] - dp[i-k][j]) % mod
                    
            dp[i][faces] = sum(dp[i][:faces]) % mod
        
        return dp[n][faces] % mod


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10**9+7
        def memo(f):
            dic = {}

            def f_alt(*args):
                if args not in dic:
                    dic[args] = f(*args)
                return dic[args]
            return f_alt

        @memo
        def find_answer(n, l):
            if n == 1:
                return 1
            if n <= 0:
                return 0
            return (find(n-1) - (find(n-rollMax[l]-1) - find_answer(n-rollMax[l]-1, l)))%mod

        @memo
        def find(n):
            if n == 0:
                return 1
            if n < 0:
                return 0
            return sum(find_answer(n, r) for r in range(6)) %mod

        return find(n)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        dp = [[0] * (faces+1) for _ in range(n+1)]
        mod = 10 ** 9 + 7
        dp[0][faces] = 1
        
        for i in range(faces):
            dp[1][i] = 1
            
        dp[1][faces] = faces
        for i in range(2, n+1):
            for j in range(faces):
                for k in range(1, rollMax[j]+1):
                    if i - k < 0:
                        break
                    dp[i][j] += (dp[i-k][faces] - dp[i-k][j]) % mod
            dp[i][faces] = sum(dp[i][:faces]) % mod
        return dp[n][faces] % mod
                    


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp=[[1]*6 for _ in range(n)]
        #dp[i][j]代表长度为i的序列，结尾为j的组合数目
        #得到所有组合减去不符合规则的
        for i in range(1,n):
            for j in range(6):
                dp[i][j]=sum(dp[i-1])
                if i==rollMax[j]:  #此时连着有j项
                    dp[i][j]-=1
                if i>rollMax[j]:
                    for k in range(6):
                        if k!=j:
                            dp[i][j]-=dp[i-1-rollMax[j]][k]
        return sum(dp[-1])%(10**9+7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10**9 + 7
        # dp[i][j] records the value of sequence of i elements with j being the last element
        dp = [[0]*7 for _ in range(n+1)]
        # initialize
        dp[0][6] = 1
        for i in range(6):
            dp[1][i] = 1
        dp[1][6] = 6
        for i in range(2,n+1):
            for j in range(6):
                for k in range(1,min(rollMax[j],i)+1):
                    dp[i][j] += dp[i-k][6]-dp[i-k][j]
                    dp[i][j] %= mod
            dp[i][6] = sum([dp[i][j] for j in range(6)])
            dp[i][6] %=mod
        return dp[n][6]
            


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MODE = 1e9+7
        f = [[0 for _ in range(7)] for _ in range(n+1)]
        f[0][6] = 1
        for i in range(1, n + 1):
            for j in range(6):
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    f[i][j] = (f[i][j] + (f[i-k][6] - f[i-k][j])%MODE)%MODE
                f[i][6] = (f[i][j] + f[i][6])%MODE
        return int(f[n][-1])

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * 7 for _ in range(n+1)]
        ans = 1
        for i in range(1, n+1):
            temp = 0
            for j, r in enumerate(rollMax):
                if i - r > 1:
                    dp[i][j] = ans - dp[i-r-1][-1] + dp[i-r-1][j]
                elif i - r == 1:
                    dp[i][j] = ans - 1
                else:
                    dp[i][j] = ans
                temp += dp[i][j]
            dp[i][-1] = temp
            ans = temp
        # print(sum(dp[4]))
        # print(dp)
        return temp % int(1e9 + 7)
#         dp = [[0] * (len(rollMax) + 1) for _ in range(n + 1)]
#         for j in range(len(rollMax)):
#             dp[1][j] = 1
#             dp[1][-1] += dp[1][j]
        
#         for i in range(2, n + 1):
#             for j in range(len(rollMax)):
#                 dp[i][j] = dp[i - 1][-1]
#                 k = i - rollMax[j]
#                 if k == 1:
#                     dp[i][j] -= 1
#                 elif k > 1:
#                     dp[i][j] -= (dp[k - 1][-1] - dp[k - 1][j])
#                 dp[i][-1] += dp[i][j]
#         print(dp)
#         return dp[n][len(rollMax)] % int(1e9 + 7)
# [[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]]


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        Q = [[0 for j in range(7)] for i in range(n+1)]
        Q[0][-1]=1
        MAX = 10**9+7
        for i in range(1,n+1):
            for j in range(6):
                if i<=rollMax[j]:
                    Q[i][j] = Q[i-1][-1]
                else:
                    for k in range(rollMax[j]):
                        Q[i][j]=(Q[i][j]%MAX+(Q[i-k-1][-1]-Q[i-k-1][j])%MAX)%MAX
                Q[i][-1]=(Q[i][-1]%MAX+Q[i][j]%MAX)%MAX
        return Q[-1][-1]

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        F = [[0 for i in range(6)] for i in range(n + 1)]
        sumF = [0 for i in range(n + 1)]
        for i in range(6):
            F[1][i] = 1
        sumF[1] = 6
        MOD = 10**9 + 7
        for i in range(2, n + 1):
            for j in range(6):
                for p in range(1, rollMax[j] + 1):
                    if i == p:
                        F[i][j] = (F[i][j] + 1) % MOD
                        continue
                    elif i > p:
                        F[i][j] = (F[i][j] + sumF[i - p] - F[i - p][j]) % MOD
                    # for k in range(6):
                    #     if j == k: continue
                    #     if i > p:
                    #         F[i][j] = (F[i][j] + F[i - p][k]) % MOD
                sumF[i] += F[i][j]

        res = 0
        for i in range(6):
            res = (res + F[n][i]) % MOD
            # print(F[n][i])
        return round(res)
        
        #1(11), 2(11), 3(11), 4(11), 5(11), 6(11) -> 6
        #1(22), 2(22), 3(22), 4(22), 5(22), 6(22) -> 6
        #1(33), 2(33), 3(33), 4(33), 5(33), 6(33) -> 6
        #


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        # dp[i][j] = rolled i times, last face is j
        # dp[i][0] = rolled i times, any face
        dp = [[0] * 7 for _ in range(n + 1)]
        
        # Base cases
        for j in range(1, 7):
            dp[1][j] = 1
        dp[0][0] = 1
        dp[1][0] = 6
        
        for i in range(2, n + 1):
            for j in range(1, 7):
                for k in range(1, min(i, rollMax[j - 1]) + 1):
                    # (i - k)th roll is not a j,
                    # so there has been i - (i - k + 1) + 1 = k j's
                    dp[i][j] = sumMod(dp[i][j], dp[i - k][0] - dp[i - k][j])
            
                dp[i][0] = sumMod(dp[i][0], dp[i][j])
        
        return dp[n][0]
    
    
def sumMod(x: int, y: int) -> int:
    return (x + y) % (10 ** 9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp, tmp, MOD = {}, {}, 10**9+7
        total, prev = [0] * 6, [0] * 6
        for k in range(n):
            for i in range(6):
                for j in range(1, rollMax[i]+1):
                    if j > 1:
                        tmp[(i, j)] = dp[(i, j-1)] if k > 0 else 0
                    else:
                        tmp[(i, j)] = (sum(prev) - prev[i]) % MOD if k > 0 else 1
                    total[i] += tmp[(i, j)]
            total, prev, dp, tmp = [0]*6, total, tmp, {}
        return sum(prev) % MOD

MAX = 10 ** 9 + 7


class Solution:
    
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        D = [[0] * 6 for i in range(n + 1)]
        D[1] = [1] * 6
        seq_nums = [0] * (n + 1)
        seq_nums[0], seq_nums[1] = 1, 6
        for i in range(2, n + 1):
            for j in range(6):
                for k in range(1, min(rollMax[j], i) + 1):
                    D[i][j] = (D[i][j] + seq_nums[i - k] + MAX - D[i - k][j]) % MAX
                    
                seq_nums[i] = (seq_nums[i] + D[i][j]) % MAX
                
        return seq_nums[-1]

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[] for i in range(6)]
        for i in range(6):
            dp[i] = [0] * rollMax[i]
            dp[i][0] = 1
        
        #print(dp)
        
        total = 6
        for i in range(1, n):
            for j in range(6):
                tmpSum = sum(dp[j])
                for k in reversed(range(1, min(rollMax[j], n))):
                    dp[j][k] = dp[j][k-1]
                dp[j][0] = total - tmpSum
            
            #print(dp)
            newTotal = 0
            for j in range(6):
                newTotal += sum(dp[j])
            total = newTotal
        
        m = pow(10, 9) + 7
        return total % m

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10 ** 9 + 7
        dp = [[0] * 7 for _ in range(n + 1)]
        dp[0][6] = 1
        for i in range(6):
            dp[1][i] = 1
        dp[1][6] = 6
        
        for i in range(2, n + 1):
            total_in_this_pos = 0
            
            for j in range(6):
                total = 0
                for k in range(max(0, i - rollMax[j]), i):
                    total += dp[k][6] - dp[k][j]
                dp[i][j] = total
                total_in_this_pos += total
            dp[i][6] = total_in_this_pos
            
            # for row in dp:
            #     print(row)
        return dp[-1][-1] % MOD
                    
                    


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10**9 + 7
        dp = [[0 for _ in range(7)] for _ in range(n)]
        for i in range(6):
            dp[0][i] = 1
            
        dp[0][6] = 6
        for i in range(1, n):
            sumi = 0
            for j in range(6):
                dp[i][j] = dp[i - 1][6]
                diff = i - rollMax[j]
                if(diff<0):
                    sumi = (sumi + dp[i][j])%mod
                else:
                    if(diff>=1):
                        remove = (dp[diff-1][6] - dp[diff-1][j] + mod)%mod
                        dp[i][j] = (dp[i][j] - remove + mod)%mod
                    else:
                        dp[i][j] = (dp[i][j] - 1)%mod
                    
                    sumi = (sumi + dp[i][j])%mod
            dp[i][6] = sumi
        
        return dp[n-1][6]

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        to_mod = 10 ** 9 + 7
        # the index end at, num of consecutive
        seq_num = [[0 for j in range(rollMax[i] + 1)] for i in range(6)]
        for i in range(6):
            if rollMax[i] > 0:
                seq_num[i][1] = 1
        for l in range(2, n + 1):
            new_seq_num = [[0 for i in range(rollMax[j] + 1)] for j in range(6)]
            seq_sum = [sum(seq_num[i]) % to_mod for i in range(6)]
            for i in range(6):
                for j in range(6):
                    if i != j:
                        new_seq_num[i][1] += seq_sum[j]
                    else:
                        for k in range(2, min(n, rollMax[i]) + 1):
                            new_seq_num[i][k] = seq_num[i][k - 1]       
            seq_num = new_seq_num
        result = 0
        for i in range(6):
            result += sum(seq_num[i])
            result = result % to_mod
        return result


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * 6 for _ in range(n)]
        prev = defaultdict(int)
        MOD = 10**9+7

        for i in range(6):
            dp[0][i] = 1
            prev[(i,1)] = 1
        
        for i in range(1, n):
            new = defaultdict(int)
            for j in range(6):
                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]
                dp[i][j] += new[(j, 1)]
                
                for k in range(1, rollMax[j]):
                    new[(j,k+1)] = prev[(j,k)]
                    dp[i][j] += new[(j,k+1)]
                dp[i][j] %= MOD
            prev = new
            
        return sum(dp[-1]) % MOD


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10**9 + 7
        
        N = n
        R = len(rollMax)
        
        # Set up DP.
        T = [0] * (N+1)
        D = [[0] * R for _ in range(N+1)]
        
        # Base cases.
        T[0] = 1
        T[1] = R
        D[1] = [1] * R
        
        # Compute.
        for i in range(2, N+1):  # Roll number.
            for j in range(R):  # Face number.
                lim = max(i - rollMax[j], 0)
                for k in range(i-1, lim-1, -1):  # num rolls given last `k` in sequence are `j`
                    D[i][j] += T[k] - D[k][j]
            T[i] = sum(D[i])
            
        return sum(D[-1]) % mod

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0 for _ in range(rollMax[i])] for i in range(6)]
        for i in range(6):
            dp[i][0] = 1
        for i in range(n - 1):
            ndp = [[0 for _ in range(rollMax[w])] for w in range(6)]
            roll_sum = [sum(i) for i in dp]
            total = sum(roll_sum)
            for j in range(6):
                ndp[j][0] = total - roll_sum[j]
                for k in range(1, rollMax[j]):
                    ndp[j][k] += dp[j][k - 1]
            dp = ndp
        return sum(sum(i) for i in dp) % (10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0] * 6 for _ in range(n+1)]
        dp[1] = [1] * 6
        for i in range(2, n+1):
            for j in range(6):
                dp[i][j] = sum(dp[i-1][j] for j in range(6))
                if i == rollMax[j]+1:
                    dp[i][j] -= 1
                elif i > rollMax[j]+1:
                    dp[i][j] -= sum(dp[i-rollMax[j]-1][k] for k in range(6) if k != j)
        return sum(dp[-1]) % (10**9+7)


from collections import defaultdict
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        if n == 1:
            return 6
        cache = {i: defaultdict(int) for i in range(6)}
        cache_new = {i: defaultdict(int) for i in range(6)}
        MOD = 10 ** 9 + 7
        
        # initialize
        for i in range(6):
            cache[i][1] = 1
        
        for i in range(2, n+1):
            for next_dice in range(6):
                # dice occ 1
                for prev_dice in range(6):
                    if prev_dice != next_dice:
                        cache_new[next_dice][1] += sum(cache[prev_dice].values())
                cache_new[next_dice][1] %= MOD
                
                # dice occ more
                for occ in range(2, rollMax[next_dice]+1):
                    cache_new[next_dice][occ] = cache[next_dice][occ-1]
            cache = cache_new
            cache_new = {i: defaultdict(int) for i in range(6)}
            
        res = 0
        for i in range(6):
            res += sum(cache[i].values())
        return res % MOD

# Refer discuss
# https://leetcode.com/problems/dice-roll-simulation/discuss/404840/Short-Python-DP-with-detailed-image-explanation
class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        # [n + 1][faces + 1] dimensional dp array
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
        # initialization
        # roll 0 times, the total combination is 1
        dp[0][faces] = 1
        # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
        # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
        
        # then roll dices from 2 times, until n times
        for i in range(2, n + 1):
            # iterate through each column (face)
            for j in range(faces):
                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]
            # update total sum of this row
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        mod = 10**9 + 7
        dp = [[0 for _ in range(7)] for _ in range(n)]
        for i in range(6):
            dp[0][i] = 1
            
        dp[0][6] = 6
        for i in range(1, n):
            sumi = 0
            for j in range(6):
                diff = i - rollMax[j]
                if(diff<0):
                    dp[i][j] = dp[i - 1][6]
                    sumi = (sumi + dp[i][j])%mod
                else:
                    if(diff>=1):
                        remove = (dp[diff-1][6] - dp[diff-1][j] + mod)%mod
                        dp[i][j] = (dp[i - 1][6] - remove + mod)%mod
                    else:
                        dp[i][j] = (dp[i - 1][6] - 1)%mod
                    
                    sumi = (sumi + dp[i][j])%mod
            dp[i][6] = sumi
        
        return dp[n-1][6]

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        
        d = [[0] * (faces + 1) for _ in range(n+1)]
        
        d[0][faces] = 1
        
        for i in range(faces):
            d[1][i] = 1
            
        d[1][faces] = sum(d[1])
        
        for i in range(2, n + 1):
            for j in range(faces):
                for k in range(1, rollMax[j] + 1):  
                    if i - k < 0:
                        break
                        
                    d[i][j] += d[i-k][faces] - d[i-k][j]
            d[i][faces] = sum(d[i])
            
        #for i in range(n+1):
        #    print(d[i])
                    
        return d[n][faces] % (10**9+7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0]*7 for x in range(n+1)]
        dp[0][-1] = 1
        for x in range(6):
            dp[1][x] = 1
        dp[1][-1] = 6
        
        for i in range(2, n+1):
            for j in range(6):
                for k in range(1, rollMax[j] + 1):
                    if i-k < 0:
                        break
                    dp[i][j] += dp[i-k][-1] - dp[i-k][j]
            dp[i][-1] = sum(dp[i])
        return dp[-1][-1] %1000000007
                    
            
            
            
            
            
            
            
            
            
    
    


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        L = len(rollMax)
        N = n
        dp = [ [0]*(L+1) for _ in range(N+1) ]      # dp[roll][index]
        
        dp[0][L] = 1
        for i in range(L):
            dp[1][i] = 1
        dp[1][L] = L
        
        # roll a dice
        for i in range(2, N+1):
            # for each faces
            for j in range(L):
                for k in range(1, rollMax[j]+1):
                    if i-k < 0:
                        break;
                    dp[i][j] += dp[i-k][L] - dp[i-k][j]
            # sum all rows
            dp[i][L] = sum(dp[i][:L])
            
        return dp[N][L] % (10**9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
#         self.rollMax = tuple(rollMax)
        
#         @lru_cache(None)
#         def helper(n, ban):
#             times = 0
#             if n == 1:
#                 for t in ban:
#                     if t > 0:
#                         times += 1
#                 return times

#             for i, t in enumerate(ban):
#                 if t > 0:
#                     cur = tuple()
#                     for j in range(len(ban)):
#                         if i == j:
#                             cur += (ban[j]-1,)
#                         else:
#                             cur += (self.rollMax[j], )
#                     times += helper(n-1, cur)

#             return times % (10**9 + 7)
        
#         return helper(n, tuple(rollMax))

        faces = len(rollMax)
        # [n + 1][faces + 1] dimensional dp array
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
        # initialization
        # roll 0 times, the total combination is 1
        dp[0][faces] = 1
        # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
        # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
        
        # then roll dices from 2 times, until n times
        for i in range(2, n + 1):
            # iterate through each column (face)
            for j in range(faces):
                # at each [i, j], trying to go up (decrease i) 
                # and collect all the sum of previous state
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]
            # update total sum of this row
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        '''
        for j = 0, 1, ..., faces - 1
        dp[i][j] means how many combinations it could be that at i-th rolling and the last face is j
        for j = faces
        dp[i][j] means how many combinations in total with i rollings
        
        '''
        faces = len(rollMax)
        # [n+1][faces+1] dimensional dp array
        dp = [[0 for _ in range(faces+1)] for _ in range(n+1)]
        
        #initialization
        # roll 0 times, the total combination is 1
        dp[0][faces] = 1
        # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
        # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
        
        # then roll dices from 2 times, until n times
        for i in range(2, n+1):
            # iterate thru each face
            for j in range(faces):
                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state
                for k in range(1, rollMax[j]+1):
                    if i-k < 0:
                        break
                    # give me all the combinations as long as the last face is not j
                    dp[i][j] += dp[i-k][faces] - dp[i-k][j]
            dp[i][faces] = sum(dp[i])
        return dp[n][faces] % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
        dp[0][faces] = 1
        for j in range(faces):
            dp[1][j] = 1 if rollMax[j] >= 1 else 0

        dp[1][faces] = sum(dp[1][j] for j in range(faces))
        for i in range(2, n + 1):
            for j in range(faces):
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        dp = [[0] * (faces + 1) for _ in range(n + 1)]
        dp[0][faces] = 1
        for j in range(faces):
            dp[1][j] = 1
        dp[1][faces] = faces
        for i in range(2, n+1):
            for j in range(faces):
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0:
                        break
                    dp[i][j] += dp[i-k][faces] - dp[i-k][j]
            dp[i][faces] = sum(dp[i])
        return dp[n][faces] % (10**9 + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        m = len(rollMax)
        dp = [[0 for j in range(m+1)] for i in range(n+1)]
        dp[0][m] = 1
        for j in range(m):
            dp[1][j] = 1
        dp[1][m] = m
        for i in range(2, n+1):
            for j in range(m):
                for k in range(1, rollMax[j]+1):
                    if i-k < 0:
                        break
                    dp[i][j] += dp[i-k][m] - dp[i-k][j]
            dp[i][m] = sum(dp[i])
        return dp[n][m]%(10**9+7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        faces = len(rollMax)
        dp = [[0] *(faces + 1) for _ in range(n+1)] 
        
        dp[0][faces] = 1
        
        for j in range(faces):
            dp[1][j] = 1
        
        dp[1][faces] = faces
        
        for i in range(2, n+1):
            for j in range(faces):
                k = 1
                while k <= i and k <= rollMax[j]:
                    dp[i][j] += dp[i-k][faces] - dp[i-k][j]
                    k += 1
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007
        
        
                


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        numFaces = len(rollMax)
        dp = [[0 for i in range(numFaces + 1)] for j in range(n + 1)]
        dp[0][numFaces] = 1
        for i in range(numFaces):
            dp[1][i] = 1
        dp[1][numFaces] = numFaces
        for i in range(2, n + 1):
            for j in range(numFaces):
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0: 
                        break
                    dp[i][j] += dp[i - k][numFaces] - dp[i - k][j]
            dp[i][numFaces] = sum(dp[i])
        return dp[n][numFaces] % 1000000007


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0]*7 for i in range(n+1)]
        dp[0][6]=1
        for i in range(6):
            dp[1][i]=1
        dp[1][6]=6
        
        for i in range(2,n+1):
            for j in range(6):
                for k in range(1,rollMax[j]+1):
                    if i-k<0:
                        break
                    dp[i][j]+=dp[i-k][6]-dp[i-k][j]
            dp[i][6] = sum(dp[i])
        return dp[-1][-1]%(10**9+7)
                


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = [[0]*7 for _ in range(n+1)]
        dp[0][6] = 1
        for i in range(6):
            dp[1][i] = 1
        dp[1][6] = 6
        for i in range(2,n+1):
            for roll in range(6):
                for j in range(1,rollMax[roll]+1):
                    if i - j < 0: break
                    dp[i][roll] += dp[i-j][6] - dp[i-j][roll]
                dp[i][6] += dp[i][roll]
        return dp[n][6] % (int(1e9) + 7)


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        
        dp = [[0 for _ in range(len(rollMax) + 1)] for _ in range(n + 1)]
        
        dp[0][-1] = 1
        dp[1] = [1] * len(rollMax) + [len(rollMax)]
        for i in range(2, n + 1):
            for j in range(len(rollMax)):
                for k in range(1, rollMax[j] + 1):
                    if i - k < 0: break
                    dp[i][j] += dp[i-k][-1] - dp[i-k][j]
            dp[i][-1] = sum(dp[i])
        return dp[-1][-1]% 1000000007

class Solution:
    def dieSimulator(self, n0, rollMax):
        nfaces = len(rollMax)
        lst = [[0] * (nfaces + 1) for _ in range(n0 + 1)]
        lst[0][-1] = 1
        for n in range(1, n0 + 1):
            for face in range(nfaces):
                for i in range(n, -1, -1):
                    if n - rollMax[face] > i:
                        break
                    lst[n][face] += lst[i][-1] - lst[i][face]
            lst[n][-1] = sum(lst[n][:-1])
        return lst[-1][-1] % (10**9 + 7)

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        
        faces = len(rollMax)
        # [n + 1][faces + 1] dimensional dp array
        dp = [[0 for i in range(faces + 1)] for j in range(n + 1)]
        
        # initialization
        # roll 0 times, the total combination is 1
        dp[0][faces] = 1
        # roll 1 times, the combinations that end at face j is 1
        for j in range(faces):
            dp[1][j] = 1
        # roll 1 times, the total combination is faces = 6
        dp[1][faces] = faces
        
        # then roll dices from 2 times, until n times
        for i in range(2, n + 1):
            # iterate through each column (face)
            for j in range(faces):
                # at each [i, j], trying to go up (decrease i) and collect all the sum of previous state
                k = 1
                while i - k >= 0 and k <= rollMax[j]:
                    dp[i][j] += dp[i - k][faces] - dp[i - k][j]
                    k+=1
            # update total sum of this row
            dp[i][faces] = sum(dp[i])
        
        return dp[n][faces] % 1000000007