893. Roll The Dice
0
Hard
Vatsal is playing a dice game. He rolls a dice and generates a random number from 1 to 6 for each roll. However, there is a new rule introduced where Vatsal cannot roll the number i more than rollMax[i] (1-indexed) consecutive times.
Given an array of integers rollMax and an integer n, you need to determine the number of distinct sequences that can be obtained with exactly n rolls.
Two sequences are considered different if at least one element differs from each other.
Please note that the answer may be very large, so return it modulo 10^9 + 7.
Input Format
The first line contains the number of rolls, n.
The second line contains an array of integers from 1 to 6, representing the maximum roll limit for each number.
Output Format
Print the number of distinct sequences that can be obtained with exactly n rolls.
Example
Input
2
1 1 2 2 2 3
Output
34
Constraints
1 <= n <= 5000
rollMax.length == 6
1 <= rollMax[i] <= 15
rollMax.length == 6
1 <= rollMax[i] <= 15
Loading...
View Submissions
Console