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: MEDIUM
Tags: Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

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 = 1000000000.0 + 7
		for i in range(1, 7):
			dp[1][i] = 1
		for i in range(2, n + 1):
			for j in range(1, 7):
				k = i - rollMax[j - 1]
				dp[i][j] = sum(dp[i - 1])
				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]
				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)
		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:
		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:

	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 = [[[0 for _ in range(16)] for _ in range(6)] for _ in range(n + 1)]
		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:
						for l in range(0, 6):
							if l == j:
								continue
							s = int(sum(dp[i - 1][l]) % (1000000000.0 + 7))
							dp[i][j][k] += s
					else:
						dp[i][j][k] += dp[i - 1][j][k - 1]
		ans = 0
		for arr in dp[n]:
			ans = ans + sum(arr)
		return int(ans % (1000000000.0 + 7))


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]:
					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(1000000000.0 + 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:
		num = [[1] * 6 + [6] for i in range(16)]
		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(1000000000.0 + 7)
			num[idxLast(0)][-1] = sum(num[idxLast(0)][:6]) % int(1000000000.0 + 7)
			pointer += 1
		return num[idxLast(1)][-1] % int(1000000000.0 + 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 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:
		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:
		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


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
		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
		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:
		dp = [[0 for c in range(6)] for r in range(n)]
		for c in range(6):
			dp[0][c] = 1
		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 = [[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:
		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
		return sum([sum(row) for row in C[-1]]) % p


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)


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):
						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


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):
			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):
					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:
		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:
		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
		return round(res)


class Solution:

	def dieSimulator(self, n: int, rollMax: List[int]) -> int:
		memo = [[0] * 6 for _ in range(n)]
		for i in range(n):
			for x in range(6):
				maxRolls = rollMax[x]
				for j in range(i - 1, i - 1 - maxRolls, -1):
					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:
		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:

		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


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)


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][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)]
		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


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)


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:
		maxAns = 10 ** 9 + 7
		krollMax = 15
		dp = [[[0] * (krollMax + 1) for i in range(6)] for j in range(n + 1)]
		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]) % 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 + 1000000000.0

		@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 = [[[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)]
		for i in range(1, 6 + 1):
			dp[1][i][1] = 1
		for i in range(2, n + 1):
			for j in range(1, 6 + 1):
				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(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)


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 = [[[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
						elif 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:
		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:

	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)]
		mod = 1000000000.0 + 7
		for i in range(6):
			dp[0][i][1] = 1
		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:
									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:
		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]
		return sum([sum(x) % (10 ** 9 + 7) for x in dp[-1]]) % (10 ** 9 + 7)


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:
		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)]
		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:
						dp[i][j][k] = sumMod(dp[i][j][k], dp[i - 1][j][k - 1])
						continue
					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
					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(1000000000.0 + 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 r in range(1, n):
			for c in range(6):
				dp[r][c] = dp[r - 1][-1]
				k = r - rollMax[c]
				if k == 0:
					dp[r][c] -= 1
				elif k >= 1:
					dp[r][c] -= dp[k - 1][-1] - dp[k - 1][c]
			dp[r][6] = sum(dp[r][:6])
		return dp[-1][-1] % int(1000000000.0 + 7)


from collections import defaultdict

class Solution:

	def dieSimulator(self, n: int, rollMax: List[int]) -> int:
		M = 10 ** 9 + 7
		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:
		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:

		@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):
						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:
		MOD = 10 ** 9 + 7
		rdim = max(rollMax)
		dp = [[[0] * rdim 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):
				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:
		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:

		@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)


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 = 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:
		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
				elif 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
		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):
					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:
		d = {}

		def dp(n, v, k):
			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)
				elif k == 2:
					d[n, v, k] = dp(n, v, 1) + dp(n - 1, v, k - 1)
				else:
					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)


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)


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)


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:

		@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)
			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:

		@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, roll_max: List[int]) -> int:
		dices = defaultdict(int, {(-1, 0): 1})
		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
					elif 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:

		@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:
				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
			return count
		rolledCount = [0] * 6
		MOD = 10 ** 9 + 7
		d = {}
		return helper(0, n, rollMax, -1, d) % MOD


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:
		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:
		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):
			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)))
			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:

		def solve(i, numConsecutive, last):
			if i == n:
				return 1
			if (i, numConsecutive, last) in memo:
				return memo[i, numConsecutive, last]
			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)


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:
		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:
		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:
				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]:
						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 dieSimulatorLast(self, n, rollMax, last, count):
		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
			elif 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)


class Solution:

	def dieSimulator(self, n, rollMax):
		if n == 1:
			return 6
		mod = int(1000000000.0 + 7)
		dp = [[[0] * 15 for j in range(6)] for i in range(n)]
		for i in range(6):
			dp[0][i][0] = 1
		for i in range(1, n):
			for p in range(6):
				for j in range(6):
					for k in range(15):
						if p != j:
							dp[i][j][0] = (dp[i][j][0] + dp[i - 1][p][k]) % mod
						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:

	def __init__(self):
		self.store = defaultdict(int)

	def rds(self, n, rm, pre, prec):
		if n == 0:
			return 1
		elif (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)


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 = [[[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(1000000000.0 + 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
				for k in range(2, rollMax[j - 1] + 1):
					dp[i][j][k] = dp[i - 1][j][k - 1]
				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
		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(1000000000.0 + 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)


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]
			rolls = 0
			for i in range(6):
				if i != value:
					rolls += roll(i, 1, left - 1)
				elif 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:
		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


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)
			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:
		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)
					elif 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:
		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:

		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)


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:
		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:
		m = max(rollMax)
		dp = [[1] + [0] * (m - 1) for _ in range(len(rollMax))]
		MOD = 1000000000.0 + 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:
				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):
			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:
		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


class Solution:

	def dieSimulator(self, n: int, rollMax: List[int]) -> int:
		self.memo = defaultdict(int)
		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)


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:
		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
			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


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)


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(1000000000.0 + 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


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
		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(1000000000.0 + 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
		for j in range(6):
			dp[0][j] = 1
		sums[0] = sum(dp[0])
		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]


class Solution:

	def dieSimulator(self, n: int, rollMax: List[int]) -> int:
		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, rollMax):
		if n == 1:
			return 6
		mod = int(1000000000.0 + 7)
		dp = [[0] * 6 for i in range(n)]
		for j in range(6):
			dp[0][j] = 1
		sums = [0] * n
		sums[0] = 6
		for i in range(1, n):
			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:
		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:
		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:
		MODE = 1000000000.0 + 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
		return temp % int(1000000000.0 + 7)


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:
		dp = [[0] * 7 for _ in range(n + 1)]
		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):
					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
		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
			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
		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
		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)
		T = [0] * (N + 1)
		D = [[0] * R for _ in range(N + 1)]
		T[0] = 1
		T[1] = R
		D[1] = [1] * R
		for i in range(2, N + 1):
			for j in range(R):
				lim = max(i - rollMax[j], 0)
				for k in range(i - 1, lim - 1, -1):
					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)


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
		for i in range(6):
			cache[i][1] = 1
		for i in range(2, n + 1):
			for next_dice in range(6):
				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
				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


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:
		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(1000000000.0) + 7)


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)