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
Loading...

View Submissions

Console