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. Since the answer may be too large, return it modulo 109 + 7.

Two sequences are considered different if at least one element differs from each other.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= n &lt;= 5000
	rollMax.length == 6
	1 &lt;= rollMax[i] &lt;= 15


class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        dp = {}
        def solve(n,last,count):
            if n == 0: return 1
            if (n,last,count) in dp: return dp[(n,last,count)]
            ans = 0
            for i in range(6):
                if last == i:
                    if count == rollMax[i]: continue
                    ans += solve(n-1,last,count + 1)
                else:
                    ans += solve(n-1,i,1)
            dp[(n,last,count)] = ans
            return ans
        
        return solve(n,None,0) % 1000000007
class Solution {
    long[][][] dp;
    int mod = 1_000_000_007;
    public int dieSimulator(int n, int[] rollMax) {
        dp = new long[n + 1][7][16];
        for(long[][] row: dp)
            for(long[] col: row)
                Arrays.fill(col, -1);

        return (int)helper(n, 0, 0, rollMax, 0);
    }

    private long helper(int n, int dice, int prev, int[] rollMax, int runs)
    {
        if(n == dice)
            return 1;

        if(dp[dice][prev][runs] != -1)
            return dp[dice][prev][runs];

        long ans = 0;
        int[] temp = rollMax;
        for(int i = 1; i <= 6; i++)
        {
            if(prev != 0 && i == prev && rollMax[i-1] <= runs)
                continue;
            if(i == prev)
                ans = (ans + helper(n, dice + 1, i, rollMax, runs + 1)) % mod;
            else
                ans = (ans + helper(n, dice + 1, i, rollMax, 1)) % mod;
        }

        dp[dice][prev][runs] = ans;
        return ans;
    }
}
class Solution {
public:

    int fun( int i , int k , int p , vector<int>& rollMax ,vector< vector< vector<int> > > &dp){
        if(i==0) return 1;
        if(dp[i][k][p]!=-1){
            return dp[i][k][p] ;
        }
         long long int ans=0 ;
        for(int j=1 ; j<7 ; j++){
            if(j==k){
            if(p<rollMax[j-1]) ans=(ans+fun(i-1,j,p+1,rollMax,dp))%1000000007 ;
            }

            else ans=(ans+fun(i-1,j,1,rollMax,dp))%1000000007 ;
        }
        return dp[i][k][p]=ans ;
    }

    int dieSimulator(int n, vector<int>& rollMax) {
       vector< vector< vector<int> > > dp(n+1, vector< vector<int> >(7 , vector<int>(16,-1)));
        int ans=fun(n,0,1,rollMax,dp) ;
        return ans ;
    }
};
/** https://leetcode.com/problems/dice-roll-simulation/
 * @param {number} n
 * @param {number[]} rollMax
 * @return {number}
 */
var dieSimulator = function(n, rollMax) {
  // Memo
  this.memo = new Map();
  
  // Modulo
  this.mod = (10 ** 9) + 7;
  
  // Keep track of roll count for each die's face (1-6)
  let currRoll = Array(6).fill(0);
  return dp(n, rollMax, n, currRoll) % this.mod;
};

var dp = function(n, rollMax, nRemain, currRoll, previous = null) {
  let key = `${nRemain}_${currRoll.toString()}`;
  
  // Base case
  if (nRemain === 0) {
    return 1;
  }
  
  // Return from memo
  if (this.memo.has(key) === true) {
    return this.memo.get(key);
  }
  
  let count = 0;
  
  // Try every face of the die, the face is the number on the die
  // The face index in array is represented by `i`
  // The face on the die (the number) is represented by `i + 1`
  for (let i = 0; i < 6; i++) {
    // Clone object we use for tracking the roll count for each die, by cloning we don't the next recursive won't change the value of current object
    let cloneRoll = [...currRoll];
    
    // Increment the count of current face
    cloneRoll[i] += 1;
    
    // This face of the die hit limit, ignore it
    if (cloneRoll[i] > rollMax[i]) {
      continue;
    }
    
    // This face of the die is different that previous one, since the limit is only for consecutive count, it means the previous face's count should be reset
    if (previous != null && i + 1 != previous) {
      cloneRoll[previous - 1] = 0;
    }
    
    // Count next recursive
    count += dp(n, rollMax, nRemain - 1, cloneRoll, i + 1) % this.mod;
  }

  // Set memo
  this.memo.set(key, count);
  
  return count;
};
Dice Roll Simulation